LeetCode Biweekly Contest 173 Discussion and Solution

Problem-by-Problem Breakdown

Problem 1 - Reverse String Prefix

Approach

Code

class Solution {
    public String reversePrefix(String s, int k) {
        StringBuilder sb = new StringBuilder();

        for(int i = k - 1; i >= 0; i--){
            char ch = s.charAt(i);
            sb.append(ch);
        }

        for(int i = k; i < s.length(); i++){
            char ch = s.charAt(i);
            sb.append(ch);
        }

        return sb.toString();
    }
}

Problem 2 - Minimum Subarray Length With Distinct Sum At Least K

Approach

Code

class Solution {
    public int minLength(int[] nums, int k) {
        int n = nums.length;

        Map<Integer, Integer> map = new HashMap<>();

        int ans = Integer.MAX_VALUE;

        int sum = 0;
        int j = 0;

        for(int i = 0; i < n; i++){
            int freq = map.getOrDefault(nums[i], 0);

            if(freq == 0){
                sum += nums[i];
            }

            map.put(nums[i], freq + 1);

            while(j <= i && sum >= k){
                ans = Math.min(ans, i - j + 1);

                int prevFreq = map.get(nums[j]);

                if(prevFreq == 1){
                    sum -= nums[j];
                }

                map.put(nums[j], prevFreq - 1);

                j++;
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

Problem 3 - Find Maximum Value in a Constrained Sequence

• a[0] is 0.
• All elements in the sequence are non-negative.
• For every index i (0 <= i <= n - 2), abs(a[i] - a[i + 1]) <= diff[i].
• For each restrictions[i] = [idx, maxVal], the value at position idx in the sequence must not exceed maxVal (i.e., a[idx] <= maxVal).

Approach

Problem 4 - Count Routes to Climb a Rectangular Grid

• '.': The cell is available.
• '#': The cell is blocked.

• You can only move from one available cell to another available cell.
• The Euclidean distance of each move is at most d, where d is an integer parameter given to you. The Euclidean distance between two cells (r1, c1), (r2, c2) is sqrt((r1 - r2)2 + (c1 - c2)2).
• Each move either stays on the same row or moves to the row directly above (from row r to r - 1).
• You cannot stay on the same row for two consecutive turns. If you stay on the same row in a move (and this move is not the last move), your next move must go to the row above.

Approach

My Contest Experience