Array

Notes and typical questions for array related problems

Notes

• Two/Three-way partition for an array. They are common techniques used in quicksort, Dutch national flag problem, and other array manipulation problems.

  // Two-way partition
  // it divides the array into 2 parts
  // elements < pivot and >= pivot (or elements <= pivot and >= > pivot), 
  // making it simple but inefficient for duplicate values.
  private int[] twoWaysPartition(int[] nums, int left, int right) {
      int pivot = nums[right];
      int i = left;
      for (int j = left; j < right; j++) {
          if (nums[j] < pivot) {
              swap(nums, i, j);
              i++;
          }
      }
      swap(nums, i, right);
      return i;
  }
  
  // Three-way partition (AKA Dutch National Flag Problem => LC 75)
  // it further splits the array into 3 parts
  // element < pivot, == pivot, and > pivot, 
  // reducing redundant swaps and improving QuickSort efficiency, especially when duplicates are common.
  private int[] threeWayspartition(int[] nums, int left, int right) {
      int pivot = nums[right];
      int i = left;
      int j = left;
      int k = right;
      while (j <= k) {
          if (nums[j] < pivot) {
              swap(nums, i, j);
              i++;
              j++;
          } else if (nums[j] > pivot) {
              swap(nums, j, k);
              k--;
          } else {
              j++;
          }
      }
      return new int[]{i,k};
  }

• For an array of length n, the number of subarrays = $1 + 2 + ... + n = n * (n + 1) / 2$

  • Reason: fixing right end r (from 1 to n), there are r choices for the left end

Typical Questions

Matrix

• 🟠 LC 59. Spiral Matrix II

  • LC solution is easier than 代码随想录, There are 4 vars representing the 4 boundaries and they keep approaching the center as the traversal

• LC 54. Spiral Matrix

  • Similar as above

  • Optimal Answer. TC: $O(m*n)$, SC: $O(1)$

• 🟠 LC 2018. Check if Word Can Be Placed In Crossword

  • It's kind of hard to implement with a clear thought

  • Optimal Solution

    • Let $m$ be the length of rows, $n$ be the length of columns, $k$ be the length of the word

    • TC: $O(m*n*k)$

    • SC: $O(1)$

• LC 48. Rotate Image

  • It's very tricky (The second time I ran into this problem, I figured it out myself!)

  • Optimal Answer. TC: $O(n^2)$, SC: $O(1)$

• ⚪ LC 36. Valid Sudoku

  • It's challenging to come up with a solution with 1 pass.

  • Optimal Answer. TC: $O(1)$, SC: $O(1)$

• ⚪ LC 73. Set Matrix Zeroes

  • It's challenging to come up with a solution that uses constant space.

  • Optimal Answer. TC: $O(m*n)$, SC: $O(1)$

• LC 289. Game of Life

  • It's challenging to come up with a solution that uses constant space. (I made it the first time I saw this problem!)

  • Optimal Answer. TC: $O(m*n)$, SC: $O(1)$

• ⚪ LC 498. Diagonal Traverse

  • Try to do it without a boolean variable.

  • Optimal Answer. TC: $O(m*n)$, SC : $O(1)$

• 🟠 LC 723. Candy Crush

  • Easy to misunderstand problem statement on when a candy can be crushed.

  • Optimal Answer. TC: $O(m^2*n^2)$, SC: $O(n)$

• LC 1304. Find N Unique Integers Sum up to Zero

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• LC 840. Magic Squares In Grid

  • Optimal Answer. TC: $O(m*n)$, SC: $O(1)$

Boyer-Moore Voting Algorithm

• 🔴 LC 169. Majority Element

  • I can't come up with this optimal solution without knowing/remembering this specific algorithm. This algorithm only works under the assumption that a majority element is guaranteed.

  • Remember this question is about finding the number which appears⌊n / 2⌋ times, but NOT the number with the highest frequency (mode).

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

Sorting Algorithm

• 🌟 LC 215. Kth Largest Element in an Array

  • 🟠 Counting Sort Solution.

    • TC: $O(n+m)$, where $n$ is the length of nums and $m$ is maxValue - minValue

    • SC: $O(m)$, $m$ is maxValue - minValue

  • 🟠 QuickSelect Solution. TC: $O(n)$, SC: $O(1)$

    • Quickselect, also known as Hoare's selection algorithm, is an algorithm for finding the $k_{th}$ smallest element in an unordered list. It is significant because it has an average runtime of $O(n)$.

    • Using the two-way partition in QuickSelect will cause TLE due to too many duplicates in some test cases, so use the three-way partition instead.

  • MinHeap Solution. TC: $O(n*log{k})$, SC: $O(k)$

• LC 274. H-Index

  • We scan citation counts from highest to lowest and keep a running total of how many papers have at least that many citations. The H-index is the first value 𝑐 for which the accumulated paper count is greater than or equal to 𝑐.

  • Approach 1 with normal sorting: Answer. TC: $O(n*logn)$, SC: $O(n)$

  • 👍 🔴 Approach 2 with Counting Sort: Optimal Answer. TC: $O(n)$, SC: $O(n)$

    • It's tough to understand...

    • 2 ideas by scanning citation counts (c) from highest to lowest and keep a running total of how many papers (papers) have at least that many citations

      • ❌ 1. Use papers: Find the last papers which papers < c. This can be a result candidate, but may not be the best result. For example, if the input is [3, 2, 2], this idea will return 1 as a result, but the real result is 2.

      • ✅ 2. Use c: Find the first c which papers ≥ c. C-based method works because c is exactly the value that must satisfy the H-index definition. papers is only used to verify it, not to produce the H-index value.

DNF algorithm

• 🟠 LC 75. Sort Colors

  • DNF algorithm (Dutch national flag problem). Read the detailed explanation of the optimal solution

  • Update: Move this question from Two Pointers section to Array section because I find it relates to the Three-way partition used in the QuickSelect algorithm.

  • Optimal Solution. TC: $O(n)$, SC: $O(1)$

Other Array Questions

• LC 1431. Kids With the Greatest Number of Candies

• 🟠 LC 1526. Minimum Number of Increments on Subarrays to Form a Target Array

  • After thinking array as a list of height values, it's easy to resolve.

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

  
• ⚪ LC 189. Rotate Array

  • Be careful for the corner case (what if k is very large).

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• 🟠 LC 41. First Missing Positive

  • It's hard to resolve it in TC $O(n)$, SC: $O(1)$. The key idea is to reuse the original array as a map.

  • Optimal Answer

    • TC: $O(n)$, the inner while loop across all iterations of the outer loop is O(n).

    • SC: $O(1)$

• LC 485. Max Consecutive Ones

  • Optimal Answer. TC: $O(n)$, SC: $O(n)$

• LC 3151. Special Array I

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 251. Flatten 2D Vector

  • Optimal Answer.

    • Let $N$ be the number of integers and $V$ be the number of cells (some could be empty) of the input

    • TC:

      • Constructor: $O(1)$

      • next(), hasNext() : $O(V/N)$

    • SC: $O(1)$

• LC 3201. Find the Maximum Length of Valid Subsequence I

  • Optimal answer. TC: $O(n)$, SC: $O(1)$

• 🔴 LC 3480. Maximize Subarrays After Removing One Conflicting Pair

  • This is too hard. No idea or even a clue at all.

  • Check this solution to understand it.

  • Optimal Answer.

    • Let $N$ be the input integer and $P$ be the number of conflicting pairs.

    • TC: $O(N+P)$, SC: $O(N)$

• LC 1762. Buildings With an Ocean View

  • Optimal Answer. TC: $O(N)$, SC: $O(N)$

• ⚪ LC 3349. Adjacent Increasing Subarrays Detection I

  • Optimal Answer. TC: $O(N)$, SC: $O(1)$

Simulation

• ⚪ LC 755. Pour Water

  • Optimal Answer. TC: $O(n*v)$, SC: $O(1)$

• LC 1929. Concatenation of Array

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$