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); }

The idea is to keep 2 pointers. trail pointer and cur pointer. The list is build in recursive function build(trail, cur) which returns last node of the list we build. build works as follows: when there is no child node: simply connect trail and cur and advance both when there is a child node, then recursively call itself with build( trail = cur, cur = cur.child ). The call would connect cur node with the list in the next level. It would return the last node in next level. Then we assign trail = last node in next level and cur = cur.next in current level. This ensures that the next iteration would connect last node in next level to next node in current level. when cur becomes null trail is the last node in current level. return trail Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 function flatten(head: _Node | null): _Node | null { const save: _Node = new _Node( -1 ); build( save, head ); if ( save.next ) save.next.prev = null; return save.next; }; function build( trail: _Node | null, cur: _Node | null ): _Node | null { while ( cur ) { if ( !cur.child ) { trail.next = cur; cur.prev = trail; trail = trail.next; cur = cur.next; } else { trail.next = cur; cur.prev = trail; const saveNext = cur.next; const lastNodeFromChildList = build( cur, cur.child ); cur.child = null; cur = saveNext; trail = lastNodeFromChildList; } } return trail; } Complexity Time complexity: $$O(n)$$ ...

DFS intuition First we must build a graph where airports are vertices and an edge airport1 -> airport2 denotes that the person travelled from airport1 -> airport2 To find a valid sequence of vertices/airports that covers all the edges/tickets, we traverse the graph using depth first search like traversal. The idea is: At each vertex, move to the next lexicographically smallest vertex. delete the edge used To maintain lexicographical order, we sort the neighbours of each vertex lexicographically. ...