Arrays 101: Big O table and techiques

Hi all,
I am in the "in-place" section at the moment from the Explore card point of view.

Attempting to summarize , in this post, what I have learnt so far with the Array 101 Explore card and also other array related problems solved by me in the past.
Perhaps this might be useful for others as well.

Big O table for quick reference:
image

Techniques
1. Two pointer technique.

  • start , end pointers. Start one pointer from beginning of array and the other one from the end.
  • slow and fast pointer. Useful for checking cycle in a list.

2. Kadane's algorithm

input : nums array of length n 
Set dp[0] = 1
for i in 1 to n - 1
dp[i] = max(dp [i - 1], 0)  + nums[i]

Useful for :

  1. Max Product Subarray
  2. Max Sum Subarray

Resources:

  • Back to Back SWE on max sub array sum

3. Prefix and suffix sum

e.g 
arr : 1 2 3 4 
prefix sum: 1 3 5 7 
suffix sum: 10 9 7 4 

Resources

In case there are other major techniques I missed or if any of the info above does not look right, please feel free to follow up in a comment below.
Thanks!

Comments (0)