loading...

Daily Coding Challenge #83

wingkwong profile image Wing-Kam ・6 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
LeetCode - Count Good Triplets

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
Where |x| denotes the absolute value of x.

Return the number of good triplets.



Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].
Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.


Constraints:

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000
*/

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        // n <= 100, brute force to find the ans
        int n = arr.size(), ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    if(
                        ( abs(arr[i]-arr[j])<=a ) && 
                        ( abs(arr[j]-arr[k])<=b ) && 
                        ( abs(arr[i]-arr[k])<=c ) 
                    ) ans++;
                }
            }
        }
        return ans;
    }
};

/*
LeetCode - Find the Winner of an Array Game
Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.



Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.
Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.
Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9
Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99


Constraints:

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr contains distinct integers.
1 <= k <= 10^9
*/

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        // iterate over all elements to check for k consecutive rounds
        int ans=max(arr[0],arr[1]);
        int cnt=1;
        for(int i=2;i<arr.size();i++){
            if(cnt==k) return ans;
            if(ans>arr[i]) cnt++;
            else {
                ans=arr[i];
                cnt=1;
            }
        }
        return ans;
    }
};

/*
LeetCode - Minimum Swaps to Arrange a Binary Grid

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:


Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:
Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1
*/

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        // find the min swaps to convert the tailing zeros in a descending order 
        // [0,1,2] --> [2,1,0]
        int n = grid.size(), ans=0;
        vector<int> v(n,0);
        // calculate how many tailing zeros for each row
        // e.g. [[0,0,1],[1,1,0],[1,0,0]] --> [0,1,2]
        for(int i=0;i<n;i++){
            for(int j=n-1;j>=0;j--){
                if(grid[i][j]==0) v[i]++;
                else break;
            }
        }
        for(int i=0;i<n;i++){
            int j=i;
            // look for the first candidate to swap
            while(j<n&&v[j]<n-1-i) j++;
            // swaps have no effect on the grid, return -1
            if(j==n) return -1;
            int jj=j;
            // swap two adjacent rows
            while(jj>i){
                swap(v[jj],v[jj-1]);
                jj--;
                ans++;
            }
        }
        return ans;
    }
};

/*
LeetCode - Get the Maximum Score

You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).
Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].
Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].
Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].
Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61


Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.
*/

class Solution {
public:
    int solve(vector<int>& nums1, vector<int>& nums2, int m, int n){
        long long i=0,j=0,ans=0,sum1=0,sum2=0,mod=1e9+7; 
        while (i<m&&j<n){ 
            // if nums1[i] < nums2[j], add to sum1 and vice vera
            if (nums1[i]<nums2[j]) sum1+=nums1[i++]; 
            else if (nums1[i]>nums2[j]) sum2+=nums2[j++]; 
            // if nums1[i] == nums2[j], add the max and reset sum1 & sum2
            else { 
                ans+=max(sum1, sum2); 
                sum1=sum2=0;
                // keep adding to ans until they are not same
                while (i<m&&j<n&&nums1[i]==nums2[j]) { 
                    ans+=nums1[i++]; 
                    j++; 
                } 
            } 
        } 
        // add remaining elements
        while (i<m) sum1+=nums1[i++]; 
        while (j<n) sum2+=nums2[j++]; 
        ans=(ans+max(sum1, sum2))%mod; 
        return ans;         
    }

    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size(), n=nums2.size();
        return solve(nums1,nums2,m,n);
    }
};

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide