Algorithm: Leetcode Contest 392

3105. Longest Strictly Increasing or Strictly Decreasing Subarray

Solution

class Solution {
    public int longestMonotonicSubarray(int[] nums) {
        
        // iterate on each element
        
        // case 1: bigger than pre: increase incresing count by 1, make decreasing count to 0
        // case 2: smaller than pre: increase descreasing count by 1, make increase count to 0;
        // case 3: equal to pre: make both increase and decrease to 0
        
        int increasing = 1, decreasing = 1, max = 1;
        
        for(int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                increasing++;
                max = Math.max(max, decreasing);
                decreasing = 1;
            } else if (nums[i] < nums[i - 1]) {
                decreasing++;
                max = Math.max(max, increasing);
                increasing = 1;
            } else {
                max = Math.max(max, increasing);
                increasing = 1;
                max = Math.max(max, decreasing);
                decreasing = 1;
            }
        }
        
        if (decreasing != 1) {
            max = Math.max(max, decreasing);
        }
        
        if (increasing != 1) {
            max = Math.max(max, increasing);
        }
        
        return max;
    }
}

Retro

Two traps in this challenge

1. the settling down after exiting the loop
2. either the increasing or decreasing number start from 1 instead of 0

3106. Lexicographically Smallest String After Operations With Constraint

Solution

class Solution {
    public String getSmallestString(String s, int k) {
        // iterate on each character
        // from left to right
        // make each character as close to 'a' as possible
        // then reduce the current distance.
        char[] chars = s.toCharArray();
        
        char[] newChars = new char[chars.length];
        int index = 0;
        char temp = 'a';
        while (k > 0 && index < chars.length) {
            temp = chars[index];
            
            if (temp == 'z') {
                k--;
                newChars[index] = 'a';
            } else {
                int disToA = getDistToA(chars[index]);
                if (k >= disToA) {
                    newChars[index] = 'a';
                    k -= disToA;
                } else {
                    newChars[index] = (char)(temp - k);
                    k = 0;
                }
                
            }
            
            index++;
        }
        
        
        while (index != chars.length) {
            newChars[index] = chars[index];
            index++;
        }
        
        return new String(newChars);
    }

    private int getDistToA(char c) {
        // clock direction
        int clockDist = c - 'a';

        // anti-clock direction
        int antiClockDist = 'z' - c + 1;

        return Math.min(clockDist, antiClockDist);
    }
    
}

Retro

1. how to calculate the distance between elements on ring

3107. Minimum Operations to Make Median of Array Equal to K

Solution

class Solution {
    public long minOperationsToMakeMedianK(int[] nums, int k) {
        Arrays.sort(nums);

        long ops = 0;
        int middle = nums.length / 2;
        
        for(int i = 0; i < middle; i++) {
            ops += Math.max(0, nums[i] - k);
        }

        ops += Math.abs(nums[middle] - k);

        for (int i = middle + 1; i < nums.length; i++) {
            ops += Math.max(0, k - nums[i]);
        }

        return ops;
    }
}

Retro

1. understand the definition of median is important, different challenge might have different definition on it
2. start from the end