Posts

Level order traversal traverse down the levels until we are 1 level above the level to be replaced. for each node in the level obtained above, set left and right node value to val, and the original leftSubtree and rightSubtree become left and right links of newly inserted left and right node respectively 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 function addOneRow( root: TreeNode|null, val: number, depth: number): TreeNode|null { if ( depth <= 1 ) { return new TreeNode( val, root, null ); } let que = [ root ]; for ( let d=1; que.length && d < depth-1; d++ ) { const LVL = que.length; for ( let j=0; j < LVL; j++ ) { const node = que.shift(); if ( node.left ) que.push( node.left ); if ( node.right ) que.push( node.right ); } } while ( que.length ) { const node = que.shift(), leftSubtree = node.left, rightSubtree = node.right; node.left = new TreeNode( val, leftSubtree, null ); node.right = new TreeNode( val, null, rightSubtree ); } return root; }; Time: $$ O(n) $$ Space: $$ O(n) $$ Recursive delegation The idea here is that if we need to update the dth level at node, then we need to update the (d-1)th level from node.left and node.right. ...

The task is to find a subarray with sum of elements = k To do this, we can build the prefix array with: $$ prefix\ [x] = \sum_{k=0}^x nums\ [k] $$ The sum of elements between subarray indices $$[i, j]$$ where $$j > i$$ is defined as: $$ prefix\ [j]\ -\ prefix\ [i-1] = \sum_{k=0}^{j} nums\ [k] - \sum_{k=0}^{i-1} nums\ [k]\ prefix\ [j]\ -\ prefix\ [i-1] = \sum_{k=i}^{j} nums\ [k] $$ ...

Explanation 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 Consider the number: [1(0), 1(1), 2(2), 3(3), 3(4), 4(5), 4(6), 8(7), 8(8)] , number(index) Here, the single number is 2, let's call it SN Note that: - For each duplicate pair that appears to the left of SN, the first occurence appears at even index and second occurence appears at odd index - For each duplicate pair that appears to the right of SN, the first occurence appears at odd index and second occurence appears at even index Now to easily detect weather we are to the left or right of SN, we can employ XOR with 1 operator. Property of XOR with 1 operator: XOR_1(x) = x ^ 1 = x + 1 , when x is even XOR_1(x) = x ^ 1 = x - 1 , when x is odd From this knowledge, it can be infered that for each index i: number[ i ] = number[ XOR_1(i) ] ,when i is to left of SN number[ i ] != number[ XOR_1(i) ] ,when i is at SN or to the right of SN For example, at i=1, i is to left of SN number[i] = number[1] = 1 == number[ XOR_1(1) ] = number[ 1-1 ] = number[0] = 1 at i=2, i is at Single Number (SN) number[2] = 2 != number[XOR_1(2)] = number[3] = 3 at i=6, i is to right of SN number[6] = 4 != number[XOR_1(6)] = number[7] = 8 You can verify this for any i Now our job is to find the minimum valud of i such that number[i] != number[XOR_1(i)] This can be done using binary search. It is worth mentioning that at i=8 in the above example number[ XOR_1(8) ] = number[ 9 ] which is out of bonds We avoid this situation by using ( i < j ) as loop condition. Which implies that i will never reach the end to make mid = 9 The binary search is designed such that j always takes valid values, where valid means nums[j] != nums[j^1] When i == j, we are at the leftmost valid index, which is exactly what we require Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 function singleNonDuplicate(nums: number[]): number { const N = nums.length; let i = 0, j = N-1; while ( i < j ) { const mid = i + Math.floor( (j-i) / 2 ); if ( nums[mid] != nums[mid^1] ) j = mid; else i = mid + 1; } return nums[j]; };

Consider the array: [0,1,1,0,0,1,1,0,1,1] The idea is to turn the 0’s into -1’s array: [-1,1,1,-1,-1,1,1,-1,1,1] Now, the task is to find a subarray with sum of elements = 0 To do this, we can build the prefix array with: $$ prefix\ [x] = \sum_{k=0}^x nums\ [k] $$ The sum of elements between subarray indices $$[i, j]$$ where $$j > i$$ is defined as: $$ prefix\ [j]\ -\ prefix\ [i-1] = \sum_{k=0}^{j} nums\ [k] - \sum_{k=0}^{i-1} nums\ [k]\ prefix\ [j]\ -\ prefix\ [i-1] = \sum_{k=i}^{j} nums\ [k] $$ ...

for each character, find the length of the longest continous substring that ends with that character for each character the number of continous substrings that end in that character = length of the longest continous substring that ends in that character ( as obtained in step 1 ) Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 function findSubstringInWraproundString(s: string): number { let curStreak = -1, lenMap = new Array(26).fill(0); for ( let i=0; i < s.length; i++ ) { if ( i > 0 && isContinous( s[i-1], s[i] ) ) curStreak++; else curStreak = 1; lenMap[ CODE(s[i]) ] = Math.max( lenMap[ CODE( s[i] ) ], curStreak ); } return lenMap.reduce( (sum, curLen) => sum += curLen, 0 ); }; function isContinous( c1: string, c2: string ) { return ( CODE(c2) - CODE(c1) + 26 ) % 26 == 1; } function CODE( c: string ) { return c.charCodeAt(0) - 'a'.charCodeAt(0); }