LeetCode Weekly Contest 486 Discussion and Solution

Problem-by-Problem Breakdown

Problem 1 - Minimum Prefix Removal to Make Array Strictly Increasing

Approach

Java Code

class Solution {
    public int minimumPrefixLength(int[] nums) {
        int n = nums.length;
        int idx = n - 1;

        while(idx > 0){
            if(nums[idx] <= nums[idx - 1]) break;
            idx--;
        }

        return idx;
    }
}

Problem 2 - Rotate Non Negative Elements

Approach

Java Code

class Solution {
    public int[] rotateElements(int[] nums, int k) {
        int n = nums.length;
        
        List<Integer> nonNeg = new ArrayList<>();

        for(int num : nums){
            if(num >= 0){
                nonNeg.add(num);
            }
        }

        int m = nonNeg.size();
        int j = 0;

        for(int i = 0; i < n; i++){
            if(nums[i] >= 0){
                nums[i] = nonNeg.get((j + k) % m);
                j++;
            }
        }

        return nums;
    }
}

Problem 3 - Pythagorean Distance Nodes in a Tree

• Let dx be the distance from u to node x
• Let dy be the distance from u to node y
• Let dz be the distance from u to node z

Approach

Java Code

class Solution {
    public void getDist(List<Integer>[] adj, int currNode, int currDist, int[] dist, boolean[] vis){

        dist[currNode] = currDist;
        vis[currNode] = true;

        for(int i = 0; i < adj[currNode].size(); i++){
            int nextNode = adj[currNode].get(i);
            if(!vis[nextNode]) getDist(adj, nextNode, currDist + 1, dist, vis);
        }
    }
    public int specialNodes(int n, int[][] edges, int x, int y, int z) {

        List<Integer>[] adj = new ArrayList[n];

        int ans = 0;

        for(int i = 0; i < n; i++){
            adj[i] = new ArrayList<>();
        }

        for(int[] edge : edges){
            int u = edge[0];
            int v = edge[1];

            adj[u].add(v);
            adj[v].add(u);
        }

        int[][] dist = new int[3][n];

        getDist(adj, x, 0, dist[0], new boolean[n]);
        getDist(adj, y, 0, dist[1], new boolean[n]);
        getDist(adj, z, 0, dist[2], new boolean[n]);

        for(int i = 0; i < n; i++){
            long[] currDist = new long[3];

            currDist[0] = dist[0][i];
            currDist[1] = dist[1][i];
            currDist[2] = dist[2][i];

            Arrays.sort(currDist);

            if(currDist[0] * currDist[0] + currDist[1] * currDist[1] == currDist[2] * currDist[2]) ans++;
        }

        return ans;
    }
}

Problem 4 - Find Nth Smallest Integer With K One Bits

Approach

My Contest Experience