Vivek
Back to Articles

Arrays – DSA Notes

9/3/2025

Clean solutions and optimal patterns for common array problems.

📌 Summary Table

ProblemApproachTime ComplexitySpace
Pascal’s TriangleBuild row by row (combinatorics or previous row)O(numRows²)O(numRows)
Two SumHashMap complement lookupO(n)O(n)
Merge Sorted Array3-pointer backward mergeO(m+n)O(1)
Maximum Subarray (Kadane)Dynamic programming (local vs global max)O(n)O(1)
Maximum Sum RectangleColumn pair + KadaneO(C²·R)O(R)
Intersection of Arrays IIFrequency mapO(n+m)O(min(n,m))
Container With Most WaterTwo pointers shrinking inwardO(n)O(1)
Best Time to Buy/Sell StockTrack min price so farO(n)O(1)
Valid SudokuHashSets for rows, cols, boxesO(81) ≈ O(1)O(1)
Search in 2D MatrixBinary search (flattened index)O(log(m·n))O(1)
Next Smallest PalindromeMirror + carry incrementO(n)O(1)
Max Points on a LineFix anchor, hash slopesO(n²)O(n)

Pascal’s Triangle

Problem.
Given an integer numRows, return the first numRows rows of Pascal’s triangle.

Idea.

  • Each row starts and ends with 1.
  • Use combinatorics (C(i,j)) or build from previous row.

Complexity.
O(numRows^2) time, O(numRows) space.

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            long val = 1; // Start with first binomial coefficient
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1); // First and last elements are always 1
                } else {
                    // C(i,j) = C(i,j-1) * (i - (j-1)) / j
                    val = (val * (i - (j - 1))) / j;
                    row.add((int) val);
                }
                if (j == 0) val = 1; // Reset val for each row
            }
            res.add(row);
        }
        return res;
    }
}

Key Takeaway. Build row-by-row using either the combinatorics formula or by summing adjacent elements of the previous row.

Two Sum

Problem. Return indices of two numbers that sum to target.

Idea.

  • Use HashMap to store seen numbers.
  • Check complement while iterating.

Complexity. O(n) time, O(n) space.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i]; // The number we want
            if (map.containsKey(need)) {
                return new int[]{map.get(need), i}; // Found
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

Key Takeaway. Store elements in a map for quick complement lookup (classic hashmap pattern).

Merge Sorted Array

Problem. Merge nums2 into nums1 (with trailing space) in sorted order.

Idea.

  • Use three pointers starting from the end.
  • Place larger element at the back.

Complexity. O(m+n) time, O(1) space.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }
        while (j >= 0) nums1[k--] = nums2[j--];
    }
}

Key Takeaway. Merge backwards to avoid overwriting elements in nums1.

Maximum Subarray (Kadane’s Algorithm)

Problem. Find the maximum sum of a contiguous subarray.

Idea.

  • Extend previous sum or start fresh at each element.
  • Track max overall.

Complexity. O(n) time.

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar = nums[0], cur = 0;
        for (int x : nums) {
            cur = Math.max(x, cur + x); // Start fresh or extend
            maxSoFar = Math.max(maxSoFar, cur);
        }
        return maxSoFar;
    }
}

Key Takeaway. Kadane’s = local max vs. global max.

Maximum Sum Rectangle in 2D Matrix

Problem. Find max sum sub-rectangle in matrix.

Idea.

  • Fix column boundaries.
  • Collapse into row sums.
  • Run Kadane’s algorithm.

Complexity. O(C^2 * R).

class Solution {
    int kadane(int[] arr) {
        int best = arr[0], cur = arr[0];
        for (int i = 1; i < arr.length; i++) {
            cur = Math.max(arr[i], cur + arr[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
    int maximumSumRectangle(int R, int C, int M[][]) {
        int ans = Integer.MIN_VALUE;
        for (int left = 0; left < C; left++) {
            int[] rowSum = new int[R];
            for (int right = left; right < C; right++) {
                for (int r = 0; r < R; r++) rowSum[r] += M[r][right];
                ans = Math.max(ans, kadane(rowSum));
            }
        }
        return ans;
    }
}

Key Takeaway. Use Kadane on row sums while iterating over column pairs.

Intersection of Two Arrays II

Problem. Return intersection of two arrays including duplicates.

Idea.

  • Count elements of nums1.
  • Reduce counts while iterating nums2.
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int x : nums1) freq.put(x, freq.getOrDefault(x, 0) + 1);
        ArrayList<Integer> out = new ArrayList<>();
        for (int y : nums2) {
            int c = freq.getOrDefault(y, 0);
            if (c > 0) {
                out.add(y);
                freq.put(y, c - 1);
            }
        }
        int[] res = new int[out.size()];
        for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
        return res;
    }
}

Key Takeaway. Use a frequency map to handle duplicates cleanly.

Container With Most Water

Problem. Find the max water area between two vertical lines.

Idea.

  • Two pointers from both ends.
  • Move inward from shorter line.
class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, best = 0;
        while (i < j) {
            best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
            if (height[i] < height[j]) i++;
            else j--;
        }
        return best;
    }
}

Key Takeaway. Two-pointer shrink based on smaller height.

Best Time to Buy and Sell Stock

Problem. Find max profit with one buy and one sell.

Idea.

  • Track minimum price.
  • Update profit at each step.
class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0], ans = 0;
        for (int p : prices) {
            min = Math.min(min, p);
            ans = Math.max(ans, p - min);
        }
        return ans;
    }
}

Key Takeaway. Maintain min price so far to compute best profit.

Valid Sudoku

Problem. Check if a 9x9 Sudoku board is valid.

Idea.

  • Use sets to check rows, cols, and sub-boxes for duplicates.
class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            HashSet<Character> rows = new HashSet<>();
            HashSet<Character> cols = new HashSet<>();
            HashSet<Character> box  = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char r = board[i][j];
                if (r != '.' && !rows.add(r)) return false;
                char c = board[j][i];
                if (c != '.' && !cols.add(c)) return false;
                int rowIndex = 3 * (i / 3);
                int colIndex = 3 * (i % 3);
                char b = board[rowIndex + j / 3][colIndex + j % 3];
                if (b != '.' && !box.add(b)) return false;
            }
        }
        return true;
    }
}

Key Takeaway. Use 3 hash sets per row, col, and box.

Search in a 2D Matrix

Problem. Search target in row-wise sorted matrix where each row’s first element > last of previous.

Idea.

  • Treat as a flattened sorted array.
  • Binary search over index space.
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int r = mid / n, c = mid % n;
            if (matrix[r][c] == target) return true;
            if (matrix[r][c] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}

Key Takeaway. Use binary search on flattened index space.

Next Smallest Palindrome

Problem. Find the next smallest palindrome greater than a number given as digits.

Idea.

  1. If all 9’s → 100...001.
  2. Mirror left to right.
  3. If mirrored ≤ original, increment middle and mirror again.
class Solution {
    private boolean all9(int[] num) {
        for (int x : num) if (x != 9) return false;
        return true;
    }
    public java.util.Vector<Integer> generateNextPalindrome(int[] num, int n) {
        java.util.Vector<Integer> res = new java.util.Vector<>();
        if (all9(num)) {
            res.add(1);
            for (int i = 0; i < n - 1; i++) res.add(0);
            res.add(1);
            return res;
        }
        int mid = n / 2;
        int i = mid - 1, j = (n % 2 == 0) ? mid : mid + 1;
        boolean leftSmaller = false;
        while (i >= 0 && num[i] == num[j]) { i--; j++; }
        if (i < 0 || num[i] < num[j]) leftSmaller = true;
        while (i >= 0) num[j++] = num[i--];
        if (leftSmaller) {
            int carry = 1;
            if (n % 2 == 1) {
                num[mid] += 1;
                carry = num[mid] / 10;
                num[mid] %= 10;
            }
            i = mid - 1;
            j = (n % 2 == 0) ? mid : mid + 1;
            while (i >= 0) {
                num[i] += carry;
                carry = num[i] / 10;
                num[i] %= 10;
                num[j++] = num[i--];
            }
        }
        for (int x : num) res.add(x);
        return res;
    }
}

Key Takeaway. Mirror left half → if not valid, increment middle and propagate carry.

Maximum Points on a Line

Problem. Find the maximum number of points on the same line.

Idea.

  • For each anchor point, compute slopes with others.
  • Normalize slope using gcd.
  • Handle duplicates separately.
class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            HashMap<String, Integer> map = new HashMap<>();
            int dup = 1, local = 0;
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                if (dx == 0 && dy == 0) { dup++; continue; }
                int g = gcd(dx, dy);
                dx /= g; dy /= g;
                if (dx < 0) { dx = -dx; dy = -dy; }
                else if (dx == 0) dy = 1;
                String key = dx + ":" + dy;
                map.put(key, map.getOrDefault(key, 0) + 1);
                local = Math.max(local, map.get(key));
            }
            ans = Math.max(ans, local + dup);
        }
        return ans;
    }
    private int gcd(int a, int b) { return b == 0 ? Math.abs(a) : gcd(b, a % b); }
}

Key Takeaway. Fix anchor → hash slopes (normalized by gcd) → handle duplicates.