- Advantages: Store multiple elements, accessing elements is fast with index
- Disadvantages: Adding/removing in the middle is slow because items must be shifted; act of copying new array is O(n) because everything must be iterated over
Be mindful about slicing or concatenating arrays in your code. Typically, slicing and concatenating arrays would take O(n) time. Use start and end indices to demarcate a subarray/range where possible.
Master the sliding window technique that applies to many subarray/substring problems. In a sliding window, the two pointers usually move in the same direction will never overtake each other. This ensures that each value is only visited at most twice and the time complexity is still O(n).
Two pointers is a more general version of sliding window where the pointers can cross each other and can be on different arrays.
When you are given two arrays to process, it is common to have one index per array (pointer) to traverse/compare the both of them, incrementing one of the pointers when relevant. For example, we use this approach to merge two sorted arrays.
- https://leetcode.com/problems/sort-colors/
- https://leetcode.com/problems/palindromic-substrings/
- https://leetcode.com/problems/merge-sorted-array/
Sometimes you can traverse the array starting from the right instead of the conventional approach of from the left.
- https://leetcode.com/problems/daily-temperatures/
- https://leetcode.com/problems/number-of-visible-people-in-a-queue/
Is the array sorted or partially sorted? If it is, some form of binary search should be possible. This also usually means that the interviewer is looking for a solution that is faster than O(n).
Can you sort the array? Sometimes sorting the array first may significantly simplify the problem. Obviously this would not work if the order of array elements need to be preserved.
- https://leetcode.com/problems/merge-intervals/
- https://leetcode.com/problems/non-overlapping-intervals/
For questions where summation or multiplication of a subarray is involved, pre-computation using hashing or a prefix/suffix sum/product might be useful.
If you are given a sequence and the interviewer asks for O(1) space, it might be possible to use the array itself as a hash table. For example, if the array only has values from 1 to N, where N is the length of the array, negate the value at that index (minus one) to indicate presence of that number.
- https://leetcode.com/problems/first-missing-positive/
- https://leetcode.com/problems/daily-temperatures/
This might be obvious, but traversing the array twice/thrice (as long as fewer than n times) is still O(n). Sometimes traversing the array more than once can help you solve the problem while keeping the time complexity to O(n).
-
Karat Songs Problem (Rust Solution) (JavaScript Solution)