weekly-contest-217

leetcode.com/contest/weekly-contest-217

Contest - LeetCode

 

 

 

leetcode.com/problems/richest-customer-wealth/

Richest Customer Wealth - LeetCode

class Solution {
    public int maximumWealth(int[][] accounts) {
        int ans = -1;
        for (int i = 0; i < accounts.length; i++) {
            int sum = 0;
            for (int money : accounts[i]) {
                sum += money;
            }
            if (sum > ans) {
                ans = sum;
            }
        }
        return ans;
    }
}

 

 

 

 

 

 

 

leetcode.com/problems/find-the-most-competitive-subsequence/

Find the Most Competitive Subsequence - LeetCode

Solution

---

Overview

The problem is to build the most competitive subsequence of size kk for a given array \text{nums}nums.

A subsequence is different from a subarray. Unlike subarray, which contains only contiguous array elements, in subsequence of an array, we can skip any number of elements given that the ordering of elements is maintained.

For array = [2,3,5,6,7,8],[5,6,7] is subarray as well as subsequence. Whereas, [5,6,8] is a subsequence but not a subarray.

For the given array, we have to generate all its subsequences with size kk and then find the one which satisfies the criteria of being most competitive. Now, what are the criteria for being the most competitive subsequence?

The most competitive subsequence is the one in which the value of the element at every position/index is smallest among values of all the subsequences at that position. Let's understand with an example.

Let nums = [2, 3, 4] and k = 2.

We could generate three subsequences of size 33 from the given nums array, seq1:[2, 3], seq2:[2, 4], seq3:[3, 4].

• Let's compare all the subsequences at index 00. seq1 and seq2 has element 22 at 0^{th}0th position. Whereas, seq3 has an element 33 which is greater than 22. Considering index 00, seq1 and seq2 can be the most competitive sequence as the value at 0^{th}0th index is smallest among other subsequences.

• Now, let's compare the remaining subsequences at index 11. seq1 has value 33 at 1^{st}1st index which is smaller than value 44 at 1^{st}1st index in seq2.

This gives us subsequence seq1:[2, 3] as the most competitive sequence among all.

Based on these insights, let's implement the solution.

---

Approach 1: Using Double-Ended Queue

Intuition

We have to choose elements for our subsequence such that every element is the smallest possible value for that array position.

The naive solution would be to generate all the possible subsequences of an array and compare the element at every position to find the most competitive subsequence. This approach is too exhaustive. What could be a better way to implement the solution?

Instead of building all the subsequences and then finding the one matching the criteria, we could scan the array and build the required subsequence. We would choose the elements for every position/index for the resultant subsequence that would be the most competitive element for that position.

For 1^{st}1st position in the resultant subsequence, we would try to choose the smallest possible value in the array, the next smaller element for the 2^{nd}2nd position, and so on. In other words, we could say that we would try to build the subsequence in Increasing Order. Any element that does not follow the order would be ignored or dropped. Let's understand all possible cases with an example.

Example, if nums = [3, 2, 5, 4] and k = 3.

We have to build the most competitive subsequence of size 33. Let's scan the array from left to right and build the result.

• index = 0 , element = 3.

  We start by choosing element 33 for the 1^{st}1st position in result, result = [3, _ , _ ].

• index = 1 , element = 2.

  We find that the next element is 22, which is smaller than last chosen element 33, hence we can drop or remove 33 and replace it by 22 at 1^{st}1st position in result, result = [2, _ , _ ].

• index = 2 , element = 5.

  Now, the current element 55 is greater than than last chosen element 22 in result, thus we could choose 55 for 2^{nd}2nd position in result, result = [2, 5, _ ].

• index = 3 , element = 4.

  Again, the current element 44 is smaller than the last chosen element 55, but this time we cannot replace 55 with 44. Because we have to build a result of size 33 and this is the last element we have. If we remove 55 at 2^{nd}2nd position in result and replace it with 44, we won't be able to find another element for 3^{rd}3rd position. Hence, we must keep 55 at the 2^{nd}2nd position and add 44 at the 3^{rd}3rd position in the result. result = [2, 5, 4].

With the above example, we can state that to build the most competitive subsequence,

• We must try to choose the smallest possible element for every position.
• We have to choose at least kk elements.

Let's understand how we can implement the intuition in detail.

Algorithm

To implement the solution discussed above, we need 2 things,

• First, we need a data structure that could hold the chosen elements for the resultant subsequence. We should be able to add or remove any number of elements from the end of the subsequence, as well as read elements at the beginning of the subsequence. The data structure that comes in our mind is Double-Ended Queue.

• Second, we need a way to know the number of elements we could drop from the array nums to build the resultant subsequence.

  For example, if nums = [3, 4, 1] and k = 3, we know that we cannot drop any element from the array, and the result would be [3, 4, 1]. Hence, there are 00 elements that can be dropped.

  If nums = [3, 4, 1, 5] and k = 3, we know that we can drop 11 element from the array as we need only 33 elements in the resultant subsequence.

  Let \text{additionalCount}additionalCount be the number of elements that we can drop from the array nums to build the result. Initially, \text{additionalCount}additionalCount would be initialized to ( length of nums array - k )

  Steps:

• Build a double-ended queue, named queue that holds the chosen subsequence at any given point.

• Iterate over array nums, choose the most competitive elements and add it to the queue.

• Compare the last element of the queue (last chosen element for the resultant subsequence) with the current element.

  • Until the last element of the queue is greater than the current element and \text{additionalCount}additionalCount is greater than 00, we know that we can remove the last chosen element from the queue and replace it with the current element which is smaller and hence a better candidate. Every time an element is removed from queue, decrement the \text{additionalCount}additionalCount by 11.

  • Otherwise, simply add the current element at the end of the queue.

• In the end, we have the most suitable candidates in the queue. Get the first kk elements from the queue and build the resultant array.

The following figure illustrates the idea for nums = [3, 6, 4, 2, 1] and k = 3.

 

 

 

 

 

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        Deque<Integer> queue = new ArrayDeque<Integer>();
        int additionalCount = nums.length - k;
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && queue.peekLast() > nums[i] && additionalCount > 0) {
                queue.pollLast();
                additionalCount--;
            }
            queue.addLast(nums[i]);
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = queue.pollFirst();
        }
        return result;
    }
}

 

 

 

 

 

 

 

leetcode.com/problems/minimum-moves-to-make-array-complementary/

Minimum Moves to Make Array Complementary - LeetCode

class Solution {
    public int minMoves(int[] nums, int limit) {
        int[] sum = new int[1+2*limit+1];
        for(int i = 0, j = nums.length-1; i< j; i++, j--){
            int x = nums[i], y = nums[j];
            
            int le = Math.min(x, y)+1, ri = Math.max(x, y)+limit;
            sum[1]+= 2;
            sum[le]--;
            sum[x+y]--;
            sum[x+y+1]++;
            sum[ri+1]++;
        }
        int ans = Integer.MAX_VALUE, total = 0;
        for(int i = 1; i<= 2*limit; i++){
            total += sum[i];
            ans = Math.min(ans, total);
        }
        return ans;
    }
}

 

 

 

 

 

 

 

leetcode.com/problems/minimize-deviation-in-array/

Minimize Deviation in Array - LeetCode

역시 HARD는 아직..