DOCSEARCHbyAlgolia
Submit Docs

LeetCode Exercise Set by xiongjiexi

website·Indexed 29 days ago

https://xiongjiexi.github.io/exercise_set/

A collection of LeetCode problem solutions and algorithmic approaches, covering topics such as monotonic stacks, prefix sums, Trie (prefix trees), priority queues, and binary search. Includes detailed analysis for problems like 2104, 1374, 380, 1475, 209, and 146.

Tokens
15.4K
Snippets
44
Records
44
Agent score
75%

What's inside LeetCode Exercise Set

  1. Calculate the Sum of Subarray Minimums using a Monotonic Stack

    To find the sum of the minimums of all possible subarrays, the problem is transformed into calculating how many subarrays each element arr[i] acts as the minimum value.

    For each element, you must determine the distance to the nearest smaller element to its left and the nearest smaller element to its right. The number of subarrays where arr[i] is the minimum is calculated as: (distance to left smaller) * (distance to right smaller).

    Key logic:

    1. Use a monotonic stack to find the boundaries (left and right) where the current element is the minimum.
    2. To handle duplicate values and avoid double-counting subarrays, use a strict inequality (<) on one side and a non-strict inequality (<=) on the other.
    3. The final result is the sum of arr[i] * left_distance * right_distance for all i, modulo $10^9 + 7$.
    class Solution {
    static int mod = (int) 1e9 + 7;
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] left = new int[n], right = new int[n];
        int[] stack = new int[n];
        int p = -1;
        for (int i = 0; i < n; i++) {
            // Maintain monotonic increasing stack
            while (p != -1 && arr[i] < arr[stack[p]]) {
                int pop = stack[p--];
                right[pop] = i - pop;
            }
            // Distance to the previous smaller element
            left[i] = p == -1 ? (i + 1) : (i - stack[p]);
            stack[++p] = i;
        }

        // Process remaining elements in stack
        while (p != -1) {
            int pop = stack[p--];
            right[pop] = n - pop;
        }
        
        long ans = 0;
        for (int i = 0; i < n; i++) 
            ans = (ans + (1L * left[i] * right[i] * arr[i] % mod)) % mod;
        return (int) ans;
    }
}

  2. Sort characters by frequency using Bucket Sort

    This approach uses bucket sort to achieve linear time complexity. It creates an array of lists where the index represents the frequency of the characters. Characters with the same frequency are grouped together in the same bucket.
    class Solution {
    public String frequencySort(String s) {
        int[] map = new int[128];
        int maxCnt = 0;
        for (char c : s.toCharArray()) {
            if (++map[(int)c] > maxCnt) maxCnt = map[(int)c];
        }
        
        List<Character>[] bucket = new List[maxCnt + 1];
        for (int i = 0; i <= maxCnt; i++) bucket[i] = new ArrayList<>();
        for (int i = 0; i < 128; i++) {
            if (map[i] != 0) {
                bucket[map[i]].add((char)i);
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int i = maxCnt; i >= 0; i--) {
            if (bucket[i].size() != 0) {
                for (char c : bucket[i]) {
                    for (int j = 0; j < i; j++) ans.append(c);
                }
            }
        }
        return ans.toString();
    }
}

  3. Find the maximum XOR of two numbers in an array using a Trie

    To find the maximum XOR value between any two numbers in an integer array, a Trie (prefix tree) can be used to store the binary representations of the numbers. For each number, the algorithm inserts it into the Trie and then searches for the number in the Trie that provides the maximum XOR result by attempting to traverse the path with the opposite bit at each position (from most significant bit to least significant bit).
    class Solution {
    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        Trie t = new Trie();
        int max = 0;
        for (int i = 0; i < n; i++) {
            t.insert(nums[i]);
            max = Math.max(max, t.search(nums[i]) ^ nums[i]);
        }
        return max;
    }

    class Trie {
        Trie[] next = new Trie[2];
        int val = -1;

        public void insert(int num) {
            int index = 31;
            int cur = num >> index;
            Trie t = this;
            while (index >= 0) {
                if (t.next[cur] == null) {
                    t.next[cur] = new Trie();
                }
                index--;
                t = t.next[cur];
                cur = (num >> index) & 1;
            }
            t.val = num;
        }

        public int search(int num) {
            Trie t = this;
            int index = 31;
            int cur = num >> index;
            int find = cur ^ 1;
            int res = 0;
            while (index >= 0) {
                if (t.next[find] != null) {
                    t = t.next[find];
                } else if (t.next[cur] != null) {
                    t = t.next[cur];
                }
                index--;
                cur = (num >> index) & 1;
                find = cur ^ 1;
            }
            res = t.val;
            return res;
        }
    }
}

  4. Calculate Subarray Range Sums using Monotonic Stack

    An optimized approach uses monotonic stacks to find the number of subarrays where each element nums[i] acts as the minimum or maximum.

    By calculating the distance to the nearest smaller element to the left and right, and the nearest larger element to the left and right, the total contribution of nums[i] to the sum of minimums and maximums can be computed as: nums[i] * (i - left) * (right - i).

    The final result is the difference between the sum of all subarray maximums and the sum of all subarray minimums: sum(max_contributions) - sum(min_contributions). This reduces the time complexity to O(n).

    class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        int[] s1 = new int[n];
        int[] s2 = new int[n];
        int t1 = -1, t2 = -1;

        long[] max = new long[n];
        long[] min = new long[n];

        for (int i = 0; i < n; i++) {
            while (t1 >= 0 && nums[i] >= nums[s1[t1]]) {
                int index = s1[t1--];
                int left = t1 >= 0 ? s1[t1] : -1;
                int right = i;
                max[index] = (long) (index - left) * (right - index);
            }
            s1[++t1] = i;

            while (t2 >= 0 && nums[i] <= nums[s2[t2]]) {
                int index = s2[t2--];
                int left = t2 >= 0 ? s2[t2] : -1;
                int right = i;
                min[index] = (long) (index - left) * (right - index);
            }
            s2[++t2] = i;
        }

        while (t1 >= 0) {
            int index = s1[t1--];
            int left = t1 >= 0 ? s1[t1] : -1;
            int right = n;
            max[index] = (long) (index - left) * (right - index);
        }

        while (t2 >= 0) {
            int index = s2[t2--];
            int left = t2 >= 0 ? s2[t2] : -1;
            int right = n;
            min[index] = (long) (index - left) * (right - index);
        }

        long maxSum = 0, maxMin = 0;
        for (int i = 0; i < n; i++) {
            maxSum += max[i] * nums[i];
            maxMin += min[i] * nums[i];
        }

        return maxSum - maxMin;
    }
}

  5. Solve the Three Sum problem using sorting and two pointers

    To find all unique triplets in an array that sum to zero, first sort the array. Iterate through the array with a fixed pointer i, and for each i, use two pointers (j starting at i+1 and k starting at the end of the array) to find pairs that sum to -nums[i]. To avoid duplicate triplets, skip identical elements for all three pointers.
    class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // Skip duplicate values for the first element
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            int t = -nums[i];
            for (int j = i + 1, k = n - 1; j < k; ) {
                // Skip duplicate values for the second element
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    j++;
                    continue;
                }
                // Skip duplicate values for the third element
                if (k != n - 1 && nums[k] == nums[k + 1]) {
                    k--;
                    continue;
                }
                int sum = nums[j] + nums[k];
                if (sum > t) {
                    k--;
                } else if (sum < t) {
                    j++;
                } else {
                    ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                }
            }
        }
        return ans;
    }
}

  6. Count subarrays with product less than K using a sliding window

    To find the number of contiguous subarrays where the product of all elements is strictly less than a given value k, use a sliding window (two-pointer) approach. Maintain a running product (multi) of the elements between the left and right pointers. When the product is less than k, the number of new valid subarrays ending at the right index is equal to the window size (right - left + 1). If the product reaches or exceeds k, shrink the window from the left until the product is again less than k or the window becomes empty.
    class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length;
        int left = 0, right = 0;
        int cnt = 0;
        int multi = 1;
        while (left <= right && right < n) {
            multi = multi * nums[right];
            if (multi < k) {
                cnt += right-left+1;
                right++;
            } else {
                multi = multi / nums[left];
                if (left == right) {
                    right++;
                    left++;
                } else {
                    left++;
                    multi = multi / nums[right];
                }
            }
        }

        return cnt;       
    }
}

  7. Implement a Trie using a 2D array for optimized performance

    This approach uses a 2D integer array trie[N][26] to simulate the tree structure, where N is the maximum number of nodes. Instead of object references, it uses integer indices to track child nodes. A separate count array tracks the number of words ending at a specific index. This method is often more performant in competitive programming contexts by avoiding object overhead.
    class Trie {
    // Maximum number of nodes
    int N = 100009;
    // 2D array to store transitions: trie[currentNode][charIndex] = nextNode
    int[][] trie;
    // Records how many words end at this node index
    int[] count;
    // Global index to allocate new nodes
    int index;

    public Trie() {
        trie = new int[N][26];
        count = new int[N];
        index = 0;
    }
    
    public void insert(String word) {
        int pos = 0;
        for (int i = 0; i < word.length(); i++) {
            int c = (int) (word.charAt(i)-'a');
            if (trie[pos][c] == 0) {
                trie[pos][c] = ++index;                
            }
            pos = trie[pos][c];
        }
        count[pos]++;
    }
    
    public boolean search(String word) {
        int pos = 0;
        for (int i = 0; i < word.length(); i++) {
            int c = (int) (word.charAt(i)-'a');
            if (trie[pos][c] == 0) {
                return false;
            }
            pos = trie[pos][c];
        }
        return count[pos] != 0;
    }
    
    public boolean startsWith(String prefix) {
        int pos = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int c = (int) (prefix.charAt(i)-'a');
            if (trie[pos][c] == 0) {
                return false;
            }
            pos = trie[pos][c];
        }
        return true;
    }
}

  8. Find the longest pair chain using a Greedy approach

    To find the longest pair chain, first sort the pairs by their first element. If the first elements are equal, sort by the second element. Iterate through the sorted pairs using a stack to maintain the current chain. If the first element of the current pair is greater than the second element of the pair at the top of the stack, add it to the chain. If it is not greater but the current pair's second element is smaller than the stack top's second element, replace the stack top with the current pair to allow more potential future pairs to fit. This approach has a time complexity of O(n log n) due to sorting.
    class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });

        Stack<int[]> stack = new Stack<>();
        for (int[] p : pairs) {
            if (stack.empty()) {
                stack.push(p);
                continue;
            }

            int[] peek = stack.peek();
            if (p[0] > peek[1]) {
                stack.push(p);
            } else if (peek[1] > p[1]) {
                stack.pop();
                stack.push(p);
            }
        }

        return stack.size();
    }
}

  9. Check if hand can be divided into consecutive groups using Sorting and HashMap

    This approach sorts the input array to easily identify the smallest available card. It uses a HashMap to track the frequency of each card. For each card in the sorted array, if it's still available, the algorithm attempts to form a consecutive sequence of length groupSize starting from that card. If any required consecutive card is missing from the map, it returns false.
    class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        Arrays.sort(hand);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < hand.length; i++) {
            map.put(hand[i], map.getOrDefault(hand[i], 0) + 1);
        }
        for (int i = 0; i < hand.length; i++) {
            int x = hand[i];
            if (!map.containsKey(x)) {
                continue;
            }

            for (int j = 0; j < groupSize; j++) {
                int num = x + j;
                if (!map.containsKey(num)) {
                    return false;
                }
                Integer cnt = map.get(num);
                if (cnt == 1) {
                    map.remove(num);
                } else {
                    map.put(num, cnt - 1);
                }
            }
        }
        return true;
    }
}

  10. Find the longest pair chain using Dynamic Programming

    The Dynamic Programming approach involves sorting the pairs by their first element. An array dp is used where dp[i] stores the length of the longest chain ending with the pair at index i. For each pair i, iterate through all previous pairs j and if the first element of pair i is greater than the second element of pair j, update dp[i] to be the maximum of its current value or dp[j] + 1. The time complexity of this approach is O(n²).
    class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int n = pairs.length;
        int[] dp = new int[n];
        int res = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

  11. Implement Beautiful Arrangement II using a parity-based placement strategy

    The goal is to construct an array of length n such that there are exactly k distinct absolute differences between adjacent elements. This specific implementation achieves this by placing numbers from 1 to k+1 in alternating positions (head and tail) to create the required differences, and then filling the remaining elements from k+2 to n in sequential order.
    class Solution {
    public int[] constructArray(int n, int k) {
        int[] res = new int[n];
        int head = 0;
        int tail = (k+1) % 2 == 0 ? k : (k-1);
        for (int i = 1; i <= n; i++) {
            if (i <= k+1) {
                if (head <= k) {
                    res[head] = i;
                    head += 2;
                } else if (tail >= 1) {
                    res[tail] = i;
                    tail -= 2;
                }
            } else {
                res[i-1] = i;
            }
        }
        return res;
    }
}

  12. Find the top K frequent words using a PriorityQueue in Java

    To find the top K most frequent words from a list, use a HashMap to count frequencies and a PriorityQueue (min-heap) to maintain the top K elements.

    Key logic for the PriorityQueue comparator:

    1. If two words have the same frequency, the word with the lexicographically larger value is placed at the top of the heap (so it can be removed first).
    2. If frequencies differ, the word with the lower frequency is placed at the top.

    When processing the map entries, if the heap size exceeds K, replace the top element if the current word has a higher frequency or the same frequency but is lexicographically smaller than the current heap top. Finally, poll all elements from the heap and reverse the list to get the result in descending order of frequency and ascending order of lexicography.

    class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String w : words) {
            map.put(w, map.getOrDefault(w, 0) + 1);
        }

        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> {
            if (map.get(a).equals(map.get(b))) {
                // Lexicographically larger words stay at the top for removal
                return b.compareTo(a);
            }
            // Lower frequency words stay at the top for removal
            return map.get(a) - map.get(b);
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (pq.size() < k) {
                pq.offer(entry.getKey());
            } else if (entry.getValue() > map.get(pq.peek()) 
                || (entry.getValue() == map.get(pq.peek()) && entry.getKey().compareTo(pq.peek()) < 0)) {
                pq.poll();
                pq.offer(entry.getKey());
            }
        }

        List<String> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.poll());
        }
        Collections.reverse(res);
        return res;
    }
}