Array - One trick problems

Writing test cases for array problems:

• array with 1 element
• array of all duplicates
• array of unique elements
• array with duplicates
• array sorted ascending
• array sorted descending

1. Trapping Rain water

https://neetcode.io/problems/trapping-rain-water Sum += if ( min(maxLeft, maxRight) - height[i] ) > 0

2. Group Anagram https://neetcode.io/problems/anagram-groups A-Z or a-z words don’t need to be sorted in nlog(n) They can be made O(1) strings and then handled And yeah, don’t forget .charChodeAt method

• The charCodeAt() method of String values returns an integer between 0 and 65535 representing the UTF-16 code unit at the given index.
• ‘a’.CharCodeAt(1) = 97, A → 65

3. No duplicate records/tuples/answer:

Sort the array and skip the equal values.

4. 3Sum - mug up

https://neetcode.io/problems/three-integer-sum two things to notice:

• how to handle “no duplicates”
• how to move pointers when we got zero
• Time complexity: O(n^2)
• Space complexity: O(1) or O(n)depending on the sorting algorithm.

5. Median of Two Sorted Array

https://neetcode.io/problems/median-of-two-sorted-arrays

• Time complexity: O(log⁡(min(n,m)))
• Space complexity: O(1)

const findMedianSortedArrays = (nums1, nums2) => {

  let A = nums1;

  let B = nums2;

  

  let total = nums1.length + nums2.length;

  

  if (nums1.length > nums2.length) {

    A = nums2;

    B = nums1;

  }

  

  let half = Math.floor(total / 2);

  

  let l = 0;

  let r = A.length - 1;

  

  while (true) {

    let midA = Math.floor((l + r) / 2);

    let midB = half - midA - 2;

  

    let ALEFT = midA >= 0 ? A[midA] : -Infinity;

    let ARIGHT = (midA + 1) < A.length ? A[midA + 1] : Infinity;

  

    let BLEFT = midB >= 0 ? B[midB] : -Infinity;

    let BRIGHT = (midB + 1) < B.length ? B[midB + 1] : Infinity;

  

    if (ALEFT <= BRIGHT && BLEFT <= ARIGHT) {

      if (total % 2 !== 0) {

        return Math.min(ARIGHT, BRIGHT);

      } else {

        return ((Math.max(ALEFT, BLEFT)) + Math.min(ARIGHT, BRIGHT)) / 2;

      }

    } else if (ALEFT > BRIGHT) {

      r = midA - 1;

    } else {

      //BLEFT > ARIGHT

      l = midA + 1;

    }

  }

}

  

console.log(findMedianSortedArrays([1, 3], [2]) === 2);

console.log(findMedianSortedArrays([1, 2], [3, 4]) == 2.5);

console.log(findMedianSortedArrays([1, 2, 3, 4], [5,6,7])===4);

6. Subarray Sum Equals K - Explanation https://www.youtube.com/watch?v=ph0v80-rRtQ

How to create Array of a particular dimensions:

1D:

const arr = Array.from({ length: 4 });

This creates [undefined, undefined, undefined, undefined].

const arr = Array.from({ length: 4 }, () => 0);

Result: [0, 0, 0, 0]

2D:

 this.prefixSum = Array.from({ length: ROWS }, () => Array(COLS).fill(0));