______ 02. Two Pointers
______ 03. Fast & Slow Pointers
______ 04. Merge Intervals
______ 05. Cyclic Sort
______ 06. In-place Reversal of a LinkedList
______ 07. Breadth First Search
______ 08. Depth First Search
______ 09. Two Heaps
______ 10. Subsets
______ 11. Binary Search
______ 12. Bitwise
______ 13. Top Kth Elements
______ 14. K-way Merge
A sliding window pattern will solve this problem in an more effecient way, time complexity O(n) - n as the size of the given array. Compared with this, a basic brute force solution will be with time complexity O(nk) - k as the number of the targeted elements.
- Exercise: Longest Substring without Repeating Characters
- Input string = "bbabcabcdd"
- Output: 4
- Explain: the longest substring w/o repeating characters is "abcd", and the length is 4.
Compared with this, a basic brute force solution will be with time complexity O(n*n), and a heapsort solution will be with O(n*logn).
- Exercise: Dutch National Flag Problem
- Input array = [2, 0, 1, 1, 1]
- Output array = [0, 1, 1, 1, 2]
- Explain: incrementally sort an array containing only three objects (labled as 0, 1 & 2)
- Exercise: Start of LinkedList Cycle
- LinkedList = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3
- starting node of cycle: 3
- Explain: Node 3 is start of cycle (3 -> 4 -> 5 -> 6 -> 3)
- Exercise: Intervals Intersection
- arr1 = [1, 3], [5, 6], [7, 9]
- arr2 = [2, 3], [5, 7]
- output : [2, 3], [5, 6], [7, 7]
- Exercise: Find all Duplicate Numbers
- nums = [3, 4, 4, 5, 5]
- output : duplicateNumbers = [4, 5]
- Exercise: Reverse a Sub-list
- start to revere, p = 2
- end to reverse, q = 4
- input-list : 1 -> 2 -> 3 -> 4 -> 5 -> null
- output-list : 1 -> 4 -> 3 -> 2 -> 5 -> null
- Exercise: Level Averages in a Binary Tree
- tree: [1] -> [2, 3] -> [4, 5, null, 7]
- avg: [1, 2.5, 5.3]
Using recursion, Depth First Search (DFS) is the approach to keep track of all the nodes while traversing.
- Exercise: Path with Correct Sequence
- tree: [1] -> [0, 1] -> [1, null, 6, 5]
- sequence: [1, 1, 6]
- output: True
Creating two heaps to store the given number stream, the time complexity of this approach will be only O(nlogn), rather than brute-force solution with time complexity O(n*n)
- Exercise: Find the Median of a Number Stream
-
- insertNum(3)
-
- insertNum(1)
-
- findMedian() -> output: 3
-
- insertNum(2)
-
- findMedian() -> output: 2
-
- insertNum(4)
-
- findMedian() -> output: 2.5
Similar with breadth-first search, this subsets approach provides a solution with time complexity O(n*n!)
- Exercise: Permutations
- Input: nums = [1,3,5]
- Output: [1,3,5], [1,5,3], [3,1,5], [3,5,1], [5,1,3], [5,3,1]
As the efficient searching algorithm, binary search provide a solution with time complexity, O(logn), for finding an item from a sorted list of items.
- Exercise: Number Range
- arr = [4, 6, 6, 6, 9], key = 6
- Output: [1, 3]
With time complexity O(n), bitwise operatioin provides a method for these problems without extra space. Compared with it, another common method is to add every numbers in the given array, but the sum will be overflowed, if the numbers in the given array are large.
- Exercise: Single Number
- arr: 1, 4, 2, 1, 3, 2, 3
- Output: 4
- Exercise: Kth Largest Number
- arr: 1, 4, 2, 1, 3, 2, 3
- Output: 4
- Exercise: Kth Smallest Number in M Sorted Lists
- list: [2, 6, 8], [3, 6, 7], [1, 3, 4]
- Kth smallest: 5
- Output: 4