Biweekly Contest 128 – 3/4

Q1: https://leetcode.com/problems/score-of-a-string/

class Solution {
    public int scoreOfString(String s) {
        char[] chars = s.toCharArray();
        int result = 0;
        for (int i=0;i<chars.length-1;i++) result = result + (int) Math.abs(chars[i] - chars[i+1]);
        return result;
    }
}

Q2: https://leetcode.com/problems/minimum-rectangles-to-cover-points/

Notes: The y values don’t matter; only the x values matter.

class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i=0; i< points.length; i++) map.put(points[i][0], map.getOrDefault(points[i][0],0)+1);
        int[] arrayKey = new int[map.size()];
        int n = 0;
        for (int i : map.keySet()) arrayKey[n++] = i;
        Arrays.sort(arrayKey);
        int result =0;
        int i = 0;
        while (i<arrayKey.length){
            n = arrayKey[i];
            while (i< arrayKey.length && arrayKey[i] < n+w+1) i++;
            result++;
        }
        return result;
    }
}

Q3: https://leetcode.com/problems/minimum-time-to-visit-disappearing-nodes/description/

Notes: Use Dijkstra’s algorithm, but only visit nodes if you can reach them before disappearance.

class Solution {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new int[]{edge[1], edge[2]});
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new int[]{edge[0], edge[2]});
        }
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{0, 0});
        boolean[] visited = new boolean[n]; // Track visited nodes to avoid revisiting
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentNode = current[0];
            if (visited[currentNode]) continue; // Skip if already visited
            visited[currentNode] = true;

            if (distance[currentNode] >= disappear[currentNode]) continue; // Skip if the node has disappeared

            for (int[] neighbor : graph.getOrDefault(currentNode, Collections.emptyList())) {
                int nextNode = neighbor[0];
                int edgeLength = neighbor[1];

                if (distance[currentNode] + edgeLength < distance[nextNode] && distance[currentNode] + edgeLength <= disappear[nextNode]) {
                    distance[nextNode] = distance[currentNode] + edgeLength;
                    pq.offer(new int[]{nextNode, distance[nextNode]});
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (distance[i] == Integer.MAX_VALUE || distance[i] >= disappear[i]) {
                distance[i] = -1;
            }
        }

        return distance;
    }
}

Q4 : https://leetcode.com/problems/find-the-number-of-subarrays-where-boundary-elements-are-maximum/

Notes: Brute force can pass, but not perfect.

class Solution {
    public long numberOfSubarrays(int[] nums) {
        HashMap<Integer, List<Integer>> positions = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            positions.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        long count = 0;
        if (positions.size() == 1) {
            return ((long) nums.length * (nums.length + 1)) / 2;
        }
        for (List<Integer> posList : positions.values()) {
            if (posList.size() > 1) {
                int consecutive = 1;
                for (int i = 1; i < posList.size(); i++) {
                    int gap = posList.get(i) - posList.get(i - 1);
                    if (gap == 1) {
                        consecutive++;
                    } else {
                        count += calculatePairs(consecutive);
                        consecutive = 1;
                    }
                }
                count += calculatePairs(consecutive) + posList.size();
            } else {
                count++;
            }
        }
        return count;
    }
    private long calculatePairs(int n) {
        return ((long) n * (n - 1)) / 2;
    }
}