Arrays
Last updated
Was this helpful?
Last updated
Was this helpful?
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. Make sure that the order of array elements do not need to be preserved before attempting a sort.
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.
Also O(n) doesn't mean you can only traverse the array once. Sometimes traversing the array more than once can help you solve the problem easily.
Are there duplicate values in the array, would it affect the answer?
When using an index to iterate through array elements, be careful not to go out of bounds.
Be mindful about slicing or concatenating arrays in your code. Typically, slicing and concatenating arrays require O(n) time. Use start and end indices to demarcate a subarray/range where possible.
Sometimes you can traverse the array from the right rather than from the left.
Master the that applies to many subarray problems.
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. For example, we use the same approach to merge two sorted arrays.
Empty sequence
Sequence with 1 or 2 elements
Sequence with repeated elements