@jedihy Hi I just did a quick look at this solution I posted long time ago. But I still think it should be O(1), because the while loop always loop 16 times, which does not change with value of num. Please correct me if I made any mistake.
ZekunWang
@ZekunWang
Posts made by ZekunWang

RE: O(1) Java solution

O(1) Java solution
/* use solution from 069  Sqrt(x), compare res * res == num time: O(16) = O(1), space: O(1) */ public boolean solution(int num) { int root = 0, bit = 1 << 15; while (bit > 0) { root = bit; if (root > num / root) { // if root * root > num root ^= bit; // set the bit back to 0 } bit >>= 1; } return root * root == num; }

does the stackoverflow test case make sense?
I have two recursion methods here:
private void recursion(char[][] board, int row, int col) { if (row < 0  row >= board.length  col < 0  col >= board[0].length) { return; } else if (board[row][col] != 'O') { return; } board[row][col] = 'V'; recursion(board, row + 1, col); recursion(board, row  1, col); recursion(board, row, col + 1); recursion(board, row, col  1); } private void recursion1(char[][] board, int row, int col) { board[row][col] = 'V'; if (row < board.length  2 && board[row + 1][col] == 'O') { recursion1(board, row + 1, col); } if (row > 1 && board[row  1][col] == 'O') { recursion1(board, row  1, col); } if (col < board[0].length  2 && board[row][col + 1] == 'O') { recursion1(board, row, col + 1); } if (col > 1 && board[row][col  1] == 'O') { recursion1(board, row, col  1); } }
They are basically the same except for some extra recursion method call to reach boundaries in first recursion method. But only the second recursion method can pass the stack overflow test case. The first one causes stack overflow because of those extra recursion calls.
If I am getting this correctly, I think they should both pass because they both traverse 'O's once. So they should not be distinguished by the stack overflow test case and I think that test case does not make sense. Otherwise, could we add another test case that the input is too big so that using recursion will cause stack overflow anyway? It should make sense because we can still use iteration + stack to fake recursion without stack overflow. Or maybe should there be no solution because using iteration + stack will reach time limit?

RE: Java O(n) Solution  Bucket Sort
@wfu PriorityQueue will need O(n log k) since pop and push will cost log k.

RE: Java O(n) Solution  Bucket Sort
one special case: if you result list only need one more element, but you next bucket has 10 elements, your solution will add 10 elements instead of picking one out of 10.

2 Solutions Analyzing the problem in different way + explanation
public class Solution { public int maxProfit(int k, int[] prices) { if (prices == null  prices.length < 2  k < 1) { return 0; } else if (k >= (prices.length + 1) / 2) { // k reach max transactions we can make, use stock problem  return maxTransaction(prices); } // 2 solutions extended from stock problem  return constantSpaceDP(prices, k); //return nSpaceDP(prices, k); } private int maxTransaction(int[] prices) { int res = 0; for (int i = 1; i < prices.length; i++) { res += Math.max(0, prices[i]  prices[i  1]); } return res; } /* sellk[i]: max profit when have sold upon p[i], total transaction is k buyk[i]: max profit when have bought upon p[i], total transaction is k ... sell2[i]: max profit when have sold upon p[i], total transaction is 2 buy2[i]: max profit when have bought upon p[i], total transaction is 2 sell1[i]: max profit when have sold upon p[i], total transaction is 1 buy1[i]: max profit when have bought upon p[i], total transaction is 1 sellk[i] = max(sellk[i  1], buyk[i  1] + p[i]) buyk[i] = max(buyk[i  1], sellk_1[i  1]  p[i])， buyk depends on previous sell k1 ... sell2[i] = max(sell2[i  1], buy2[i  1] + p[i]) buy2[i] = max(buy2[i  1], sell1[i  1]  p[i])， buy2 depends on previous sell1 sell1[i] = max(sell1[i  1], buy1[i  1] + p[i]) buy1[i] = max(buy1[i  1], p[i]) optimization: space O(kn) > O(k) */ private int constantSpaceDP(int[] p, int k) { int[] trans = new int[k * 2]; for (int i = 1; i < trans.length; i += 2) { trans[i] = Integer.MIN_VALUE; } for (int tp : p) { for (int i = 0; i < trans.length;) { trans[i] = Math.max(trans[i], trans[++i] + tp); trans[i] = Math.max(trans[i], (++i < trans.length ? trans[i] : 0)  tp); } } int res = 0; for (int i = 0; i < trans.length; i += 2) { res = Math.max(res, trans[i]); } return res; } /* M[i][j]: max profit of ith transaction from day 0 to day j M[i][j] = max(M[i][j  1], max(M[i  1][k] + p[j]  p[k])), k from 0 to j  1 = max(M[i][j  1], p[j] + max(M[i  1][k]  p[k])) = max(M[i][j  1], p[j] + tmp); tmp = Math.max(tmp, M[i  1][j]  p[j]); optimization: space O(m*n) > O(n) */ private int nSpaceDP(int[] p, int k) { int[] M = new int[p.length]; for (int i = 1; i <= k; i++) { int tmp = M[0]  p[0], top; for (int j = 1; j < p.length; j++) { top = M[j]; M[j] = Math.max(M[j  1], tmp + p[j]); tmp = Math.max(tmp, top  p[j]); } } return M[p.length  1]; } }

2 Solutions Analyzing the problem in different way + explanation
public class Solution { public int maxProfit(int[] prices) { if (prices == null  prices.length < 2) { return 0; } return constantSpaceDP(prices); //return nSpaceDP(prices); //return mnSpaceDP(prices); } /* sell2[i]: max profit when have sold upon p[i], total transaction is 2 buy2[i]: max profit when have bought upon p[i], total transaction is 2 sell1[i]: max profit when have sold upon p[i], total transaction is 1 buy1[i]: max profit when have bought upon p[i], total transaction is 1 sell2[i] = max(sell2[i  1], buy2[i  1] + p[i]) buy2[i] = max(buy2[i  1], sell1[i  1]  p[i])， buy2 depends on previous sell1 sell1[i] = max(sell1[i  1], buy1[i  1] + p[i]) buy1[i] = max(buy1[i  1], p[i]) optimization: space O(4n) > O(4) */ private int constantSpaceDP(int[] p) { int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0; for (int tp : p) { sell2 = Math.max(sell2, buy2 + tp); buy2 = Math.max(buy2, sell1  tp); sell1 = Math.max(sell1, buy1 + tp); buy1 = Math.max(buy1, tp); } return Math.max(sell1, sell2); } /* M[i][j]: max profit of ith transaction from day 0 to day j M[i][j] = max(M[i][j  1], max(M[i  1][k] + p[j]  p[k])), k from 0 to j  1 = max(M[i][j  1], p[j] + max(M[i  1][k]  p[k])) = max(M[i][j  1], p[j] + tmp); tmp = Math.max(tmp, M[i  1][j]  p[j]); optimization: space O(m*n) > O(n) */ private int nSpaceDP(int[] p) { int[] M = new int[p.length]; for (int i = 1; i < 3; i++) { int tmp = M[0]  p[0], top; for (int j = 1; j < p.length; j++) { top = M[j]; M[j] = Math.max(M[j  1], tmp + p[j]); tmp = Math.max(tmp, top  p[j]); } } return M[p.length  1]; } private int mnSpaceDP(int[] p) { int[][] M = new int[3][p.length]; for (int i = 1; i < 3; i++) { int tmp = M[i  1][0]  p[0]; for (int j = 1; j < p.length; j++) { M[i][j] = Math.max(M[i][j  1], tmp + p[j]); tmp = Math.max(tmp, M[i  1][j]  p[j]); } } return M[2][p.length  1]; }
}

Confusion about "constant space"
Hi, I am confused about the definition of "constant space". As far as I know, space complexity is the total space excluding result that has been used to solve the problem. So when we use recursion, shouldn't we take the stack memory space of the recursion path into consideration? If so, using mergesort for this problem should costs O(log n) + O(1) = O(log n) space, assuming n is the length of the list.
If I am in a interview, does the interviewer expect me to say O(log n) or O(1)?

RE: C++ 16ms simple solution
I don't think those existing nodes are in stack. Please see my example:
ListNode* fun1(){ ListNode *head = new Node(10), *tmp = head; int n = 10; while(n){ tmp>next = new Node(n); tmp = tmp>next; } //10 to 1 deleteNode(head); //9 to 1, deleteNode() need to delete a node from the heap return head; //return list to caller function }
You have to use "delete", otherwise it is memory leak. When deleteNode() returns, "tmp" is destroyed in deleteNode() and you will never find that node again.