Notice that the statement inside the while loop can run at most n times. Overall order is still O(n).
L
lasthope
@lasthope
5
Reputation
7
Posts
99
Profile views
0
Followers
0
Following
Posts made by lasthope

RE: Simple O(n) greedy solution

RE: Very simple solution using clockwise direction variable
Not really. It's making a clockwise spiral like turn, never trying to reach the 0 boundary, given n > 1.

Simple O(n) greedy solution
class Solution { public: int jump(int A[], int n) { vector<int> step(n, 0); for(int i = 0, l = 1; i < n; i++) // l represents the first unexplored step while(l < n && l  i <= A[i]) // decide if we can make the jump to l step[l++] = step[i] + 1; // "the first time we reach position l" is the min # of necessary steps return step[n1]; } };

Find maximum, then increasing sequence from left and right up to the maximum
class Solution { public: int trap(int A[], int n) { int max_ind = max_element(A, A+n)  A; int l = 0, w = 0; for(int i=1; i<=max_ind; i++){ if(A[i] < A[l]) w += (A[l]  A[i]); else l = i; } l = n  1; for(int i=n2; i >= max_ind; i){ if(A[i] < A[l]) w += (A[l]  A[i]); else l = i; } return w; } };
 Find the index of the first maximum value.
 Look for increasing sequence from left up to the max. Add as much water as you can.
 Do the same as step 2 from right to left.
Sharing this since I thought it would be simpler to understand.

Very simple solution using clockwise direction variable
In case anyone is interested in a simple direction based solution...
class Solution { public: vector<vector<int> > generateMatrix(int n) { vector<vector<int> > res(n, vector<int>(n, 0)); if( n == 1 ) res[0][0] = 1; if(n <= 1) return res; int dx[] = {0, 1, 0,1}, dy[] = {1, 0,1, 0}; int d = 0, i = 0, j = 0, v = 1; while(true){ res[i][j] = v++; if( i + dx[d] == n  j + dy[d] == n  res[ i + dx[d] ][ j + dy[d] ]) d = (d+1)%4; i += dx[d], j += dy[d]; if(res[i][j]) break; } return res; } };

Simple O(k) solution
class Solution { public: vector<int> getRow(int k) { vector<int> res(k+1, 1); for(int i=1; i<k; i++) res[i] = ( (long long)res[i1] * (k+1i) ) / i; return res; } };
I saw couple of over complicated solutions here. So, I thought I would share mine. It won't work for large values of k though.