Leetcode Biweekly Contest 103

Problem 1 - https://leetcode.com/contest/biweekly-contest-103/problems/maximum-sum-with-exactly-k-elements/

Solution:

class Solution {
    public int maximizeSum(int[] nums, int k) {
        // Only the max element will be changed every time
        int max = Integer.MIN_VALUE;
        for(int i=0; i<nums.length; i++) {
            if(nums[i]>max){
                max = nums[i];
            }
        }
        // This is AP sum with starting number as max element, and common difference of 1 and k elements taken
        int sum = ((2*max + (k-1))*k) / 2 ;
        return sum;
    }
}

Problem 2 - https://leetcode.com/contest/biweekly-contest-103/problems/find-the-prefix-common-array-of-two-arrays/

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int prefixSum[] = new int[A.length];
        // Hashset will keep count of unique elements found so far, if the unique elements are less than the numbers encountered in both arrays so far, it means we have something common, which we will store in the prefixSum array
        HashSet<Integer> hset = new HashSet<>();

        for(int i=0; i<A.length; i++) {
            hset.add(A[i]);
            hset.add(B[i]);
            prefixSum[i] = (i+1)*2 - hset.size();
        }

        return prefixSum;

    }
}

Problem 3 - https://leetcode.com/contest/biweekly-contest-103/problems/maximum-number-of-fish-in-a-grid/

For the first example, look at the below diagram - we have four water bodies with total number of fish as - 3, 5, 7, 5, and the maximum of it is 7 - and this is the answer.

Here we will use BFS for all the water bodies, and we will also keep an outer for loop to traverse the matrix, as water bodies are not connected, we may have to visit the next node by traversing the array.

class Solution {
    public int findMaxFish(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        // This will store the final answer
        int max = 0;
        // The array to keep track of visited nodes in the matrix
        boolean visited[][] = new boolean[m][n];

        // traverse the entire matrix and if any node is already visited, ignore or if the node's value is 0, then also ignore
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) { 
                if(visited[i][j]==true)
                    continue;
                if(grid[i][j]==0)
                    continue;
            // This queue will keep track of the current water body
                Queue<Pair<Integer, Integer>> q = new LinkedList<>();
                Pair<Integer, Integer> pair = new Pair(i,j);

                q.add(pair);
                visited[i][j] = true;
                int localSum = 0;
                // while we have something in our water body, keep adding elements around of it and keep getting the sum of elements one by one by removing from the queue
                while(!q.isEmpty() ) {
                    int sizeAtlevel = q.size();
                    Pair<Integer, Integer> p = q.poll();
                    int x = p.getKey();
                    int y = p.getValue();
                    localSum += grid[x][y];
                    for(int in=0; in<sizeAtlevel; in++) {
                        if(x+1<m) {
                            if(!visited[x+1][y] && grid[x+1][y]!=0)
                            {
                                q.add(new Pair(x+1,y));
                                visited[x+1][y] = true;
                            }
                        }
                        if(y+1<n) {
                            if(!visited[x][y+1] && grid[x][y+1]!=0)
                            {
                                q.add(new Pair(x,y+1));
                                visited[x][y+1] = true;
                            }
                        }
                        if(x>0) {
                            if(!visited[x-1][y] && grid[x-1][y]!=0)
                            {
                                q.add(new Pair(x-1,y));
                                visited[x-1][y] = true;
                            }
                        }
                        if(y>0) {
                            if(!visited[x][y-1] && grid[x][y-1]!=0)
                            {
                                q.add(new Pair(x,y-1));
                                visited[x][y-1] = true;
                            }
                        }
                    }
                }
               // if the sum of current waterbody is more than the max, modify the max
                if(max<localSum)
                    max = localSum;}
        }
        return max;
    }
}

Problem 4 - https://leetcode.com/contest/biweekly-contest-103/problems/make-array-empty/

P.S. - Explanation to be added soon

import java.util.Arrays;
import java.util.Comparator;

class Solution {

    int[] a;
    void init(int n) {
        a = new int[n + 1];
    }
    void add(int idx, int value) {
        while (idx < a.length) {
            a[idx] += value;
            idx += idx & -idx;
        }
    }
    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += a[idx];
            idx -= idx & -idx;
        }
        return sum;
    }

    public long countOperationsToEmptyArray(int[] nums) {
        int[][] data = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            data[i][0] = nums[i];
            data[i][1] = i + 1;
        }
        Arrays.sort(data, Comparator.comparingInt(x -> x[0]));
        init(nums.length);
        for (int i = 1;i <= nums.length;i++) {
            add(i, 1);
        }
        long ans = 0;
        int res = 1;
        for (int[] row: data) {
            int idx = row[1];
            int t;
            if (idx >= res) {
                t = query(idx - 1) - query(res - 1) + 1;
            } else {
                t = (query(nums.length) - query(res - 1) + query(idx - 1)) + 1;
            }
            ans += t;
            add(idx, -1);
            res = idx;
        }
        return ans;
    }
}