[LeetCode] All Divisions With the Highest Score of a Binary Array

Problem: You are given a 0-indexed binary array nums of length n. nums can be divided at index i (where 0 <= i <= n) into two arrays (possibly empty) numsLeft and numsRight:

• numsLeft has all the elements of nums between index 0 and i - 1 (inclusive), while numsRight has all the elements of nums between index i and n - 1 (inclusive).
• If i == 0, numsleft is empty, while numsright has all the elements of nums.
• If i == n, numsleft has all the elements of nums, while numsright is empty.

The division score of an index i is the sum of the number of 0's in numsLeft and the number of 1's in numsRight.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Example:

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: numsleft is [0]. numsright is [0,1,0]. The score is 1 + 1 = 2.
- 2: numsleft is [0,0]. numsright is [1,0]. The score is 2 + 1 = 3.
- 3: numsleft is [0,0,1]. numsright is [0]. The score is 2 + 0 = 2.
- 4: numsleft is [0,0,1,0]. numsright is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.

Input: nums = [0,0,0]
Output: [3]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
- 1: numsleft is [0]. numsright is [0,0]. The score is 1 + 0 = 1.
- 2: numsleft is [0,0]. numsright is [0]. The score is 2 + 0 = 2.
- 3: numsleft is [0,0,0]. numsright is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.

Input: nums = [1,1]
Output: [0]
Explanation: Division at index
- 0: numsleft is []. numsright is [1,1]. The score is 0 + 2 = 2.
- 1: numsleft is [1]. numsright is [1]. The score is 0 + 1 = 1.
- 2: numsleft is [1,1]. numsright is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.

Approach: The problem is simple, we iterate through the the array we need to maintain number of 0s at the left and number of 1s on the right. Now how we can quickly calculate it?

The number of 1s on the right will be the sum of array minus the number of 1s on the left. To calculate the number of 1s quickly we can maintain prefix array sum. Now you can see the calculation:

• Number of 0s on the left at index i = i  - prefixSum[i - 1] 
• prefixSum[i - 1] will tell the number of 1s at the left
• If we subtract the prefixSum[i - 1] from i, it will tell the number of 0s on the left
• Number of 1s on the right at index i = SUM(nums) - prefixSum[i - 1]

Now we just need to calculate the maximum of the sum of above two values at each index i and return all the i's which has the maximum sum.

Implementation in C#:

    public IList<int> MaxScoreIndices(int[] nums)

    {

        IList<int> result = new List<int>();

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return result;

        }

        int arrSum = nums[0];

        for (int i = 1; i < length; ++i)

        {

            arrSum += nums[i];

            nums[i] += nums[i - 1];

        }

        int maxScore = arrSum;

        result.Add(0);

        for (int i = 1; i < length; ++i)

        {

            int currScore = i - nums[i - 1];

            currScore += (arrSum - nums[i - 1]);

            if (currScore > maxScore)

            {

                maxScore = currScore;

                result = new List<int>();

                result.Add(i);

            }

            else if (currScore == maxScore)

            {

                result.Add(i);

            }

        }

        int lastScore = length - arrSum;

        if (lastScore > maxScore)

        {

            maxScore = lastScore;

            result = new List<int>();

            result.Add(length);

        }

        else if (lastScore == maxScore)

        {

            result.Add(length);

        }

        return result;

    }

Complexity: O(n)

[LeetCode] Minimum Cost of Buying Candies With Discount

Problem: A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

• For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.

Example:

Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Approach: The question is to get the minimum cost possible. Given we can exclude the cost of every third candy, we need to exclude the maximum cost candy possible. Given we can only exclude a candy from the triplet if the cost of other two candies are more or equal to the excluded candy. That means we can exclude 3rd maximum, 6th maximum, 9th maximum and so on.

Given we need to exclude the maximum cost candy possible given the above condition, what we can do is to sort the array in descending order and then it becomes simple to exclude cost[2], cost[5], cost[8] and so on. Remaining sum of the array is our answer.

Implementation in C#:

    public int MinimumCost(int[] cost)

    {

        int length = cost?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        Array.Sort(cost, (i, j) => {

            return j.CompareTo(i);

        });

        int minCost = 0;

        for (int i = 1; i <= length; ++i)

        {

            if (i % 3 == 0)

            {

                continue;

            }

            minCost += cost[i - 1];

        }

        return minCost;

    }

Complexity: O(nlogn)

[LeetCode] Array Partition

Problem: Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Example:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Approach: The catch here is to get the maximum sum possible. That means we need to get the maximum n values possible from the array but the problem here is we need to get the minimum value of the pair so what we can get is 2nd maximum, 4th maximum, 6th maximum and so on.

To get this efficiently, we can sort the array and then take nums[0], nums[2], nums[4] and so on. We just need to add these values and return it.

Implementation in C#:

    public int ArrayPairSum(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0 || length % 2 != 0)

        {

            return 0;

        }

        Array.Sort(nums);

        int sum = 0;

        for (int i = 0; i < length; i += 2)

        {

            sum += nums[i];

        }

        return sum;

    }

Complexity: O(nlogn)

[LeetCode] Minimum Difference Between Highest and Lowest of K Scores

Problem: You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Example:

Input: nums = [90], k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
- [90]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.

Approach: We have to find the maximum and minimum value of each k size subarray so we can sort the array. Now what we just need to do is to take the subarray in sequence like nums[0...k-1], nums[1...k], nums[2...k+1] etc. Now if you see its easy to find the max and min value of these subarray as 1st value will be the minimum value and last value is the maximum value.

Now we just need to take the difference of these value and get the minimum of these differences which will be our answer.

Implementation in C#:

    public int MinimumDifference(int[] nums, int k)

    {

        int length = nums?.Length ?? 0;

        if (k > length)

        {

            return 0;

        }

        Array.Sort(nums);

        int min = int.MaxValue;    

        for (int i = 0; i + k <= length; ++i)

        {

            if (min > nums[i + k - 1] - nums[i])

            {

                min = nums[i + k - 1] - nums[i];

            }

        }

        return min;    

    }

Complexity: O(nlogn)