153. Minimum in Rotated Sorted Array

Approach

A rotated sorted array is formed by shifting elements from the end to the beginning. For instance, rotating [0,1,2,4,5,6,7] four times yields [4,5,6,7,0,1,2]. To find the minimum element efficiently, use binary search. Compare the middle element with the rightmost element:

• If arr[mid] < arr[right], the right half is sorted, so the minimum must lie in the left half (including mid).
• Otherwice, the left half is sorted, and the minimum is in the right half (excluding mid).

Implementation

class Solution {
    public int findMin(int[] arr) {
        int low = 0, high = arr.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < arr[high]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return arr[low];
    }
}

452. Minimum Arrows to Burst Balloons

Approach

To minimize the number of arrows, sort balloons by their end coordinates. Place the first arrow at the end of the first balloon. For subsequent balloons:

• If a balloon starts before or at the current arrow position, it is burst by the same arrow.
• Otherwise, place a new arrow at the end of the current balloon.

Sorting by end positions ensures maximum overlap coverage with each arrow.

Implementation

import java.util.Arrays;

class Solution {
    public int findMinArrowShots(int[][] balloons) {
        if (balloons.length == 0) return 0;
        
        Arrays.sort(balloons, (a, b) -> Integer.compare(a[1], b[1]));
        
        int arrows = 1;
        int currentEnd = balloons[0][1];
        
        for (int[] b : balloons) {
            if (b[0] > currentEnd) {
                arrows++;
                currentEnd = b[1];
            }
        }
        return arrows;
    }
}

131. Palindrome Partitioning

Approach

Use backtracking to partition the string in to all possible palindromic substrings. For each starting index, expand the end index to form substrings. Check if a substring is a palindrome using memoization to avoid redundant checks. Recursively process the remaining string after each valid partition.

Memoization stores palindrome status for substrings to optimize repeated checks:

• dp[i][j] = 1 if substring from i to j is a palindrome.
• dp[i][j] = -1 if not.
• Recursively compute based on character matches and inner substring status.

Implementation

import java.util.*;

class Solution {
    private List<List<String>> results;
    private List<String> current;
    private int[][] dp;
    private int n;
    
    public List<List<String>> partition(String s) {
        n = s.length();
        dp = new int[n][n];
        results = new ArrayList<>();
        current = new ArrayList<>();
        
        backtrack(s, 0);
        return results;
    }
    
    private void backtrack(String s, int start) {
        if (start == n) {
            results.add(new ArrayList<>(current));
            return;
        }
        
        for (int end = start; end < n; end++) {
            if (isPalindrome(s, start, end) == 1) {
                current.add(s.substring(start, end + 1));
                backtrack(s, end + 1);
                current.remove(current.size() - 1);
            }
        }
    }
    
    private int isPalindrome(String s, int i, int j) {
        if (dp[i][j] != 0) return dp[i][j];
        if (i >= j) dp[i][j] = 1;
        else if (s.charAt(i) == s.charAt(j)) 
            dp[i][j] = isPalindrome(s, i + 1, j - 1);
        else 
            dp[i][j] = -1;
        return dp[i][j];
    }
}