Array Problems

1 minute read

For Arrays, Strings and Lists

  • For Array, length is a field - array.length
  • For String, length is a method - str.length()
  • List has a size method = list.size()

Single Pointer Technique

  • Iterate through LEFT
  • Iterate through RIGHT
    • int idx = arr.length-1
    • int idx = list.size()-1
  • Use an ADDITIONAL ARRAY of same size (Space complexity O(N), where N = size of the array
  • Optimize the additional Array to use a single variable

Two Pointer Technique

  • One begins from left/start, other from the right end.
  • The while loop
    int left = 0, right = str.length() - 1;
    while(left < right){
        left++;
        right--;
      }
    
  • The for loop
    for(int low = 0, high = s.length-1; low < high; low++,high--){
    
Left pointer and Right pointer movements based on if condition.
Find count of given Sum in all pairs in the Array

Checks

if (array size < 2)
    return 0;

Approach 1 : Greedy approach to test all the possible combinations exhaustively

Approach 2 : Two pointer Approach - Test only those possible combinations that makes sense

Approach 3 : Hash map and variant approach

Left & Right Array approach

Create two temporary arrays,

  • one left that takes computation of elements to the left, upto the current element.
  • Same for Right array.
Replace each element with the greatest element to the Right in an Array

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/

Replace a number with product of all other without division

https://leetcode.com/problems/product-of-array-except-self/

Trapping Rain Water

Trapping Rain Water Problem

left[i] = Math.max(left[i-1], arr[i]);//arr[i] means including current element
right[i] = Math.max(right[i+1], arr[i]);
result = result + Math.min(left[i],right[i]) - arr[i];

Sliding Window Approach