-
Notifications
You must be signed in to change notification settings - Fork 2.5k
Description
Bug Report for https://neetcode.io/problems/reverse-integer
The brute solution given is not actually O(1) time and O(1) space. It is O(log n) time and space complexity. Mistake in documentation.
Neetcode Brute Force Solution:
class Solution {
/**
* @param {number} x
* @return {number}
*/
reverse(x) {
const org = x;
x = Math.abs(x);
let res = parseInt(x.toString().split('').reverse().join(''));
if (org < 0) {
res *= -1;
}
if (res < -(2 ** 31) || res > 2 ** 31 - 1) {
return 0;
}
return res;
}
}
-
str.split('').reverse().join('') - O(d)
split(''): Creates array of d characters - O(d)
reverse(): Reverses d characters - O(d)
join(''): Joins d characters back - O(d)
Total: O(d) + O(d) + O(d) = O(d)
TIme: O(log n) -
parseInt(reversed) - O(d)
Parsing a string of d digits takes O(d) time
Total Time: O(d) + O(d) + O(d) = O(d) = O(log n)
let res = parseInt(x.toString().split('').reverse().join('')); // O(d) space - string of d characters
Space : O(log n)