Biweekly Contest 70 LeetCode Solution

Problem 1 – Minimum Cost of Buying Candies With Discount Leetcode Solution

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 123, 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 1:

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.

Example 2:

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.

Example 3:

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.

Constraints:

  • 1 <= cost.length <= 100
  • 1 <= cost[i] <= 100

Minimum Cost of Buying Candies With Discount Leetcode Solution in JavaScript

var minimumCost = function(cost) {
    if (cost.length < 3) {
        return cost.reduce((prev, cur) => prev + cur);
    }
    
    cost.sort((a, b) => b - a);
    let count = 0;
    let sum = 0;
    
    for (const num of cost) {
        if (count === 2) {
            count = 0;
            continue;
        }
        sum += num;
        count++;
    }
    
    return sum;
};

Minimum Cost of Buying Candies With Discount Leetcode Solution in Java

    public int minimumCost(int[] A) {
        Arrays.sort(A);
        int res = 0, n = A.length;
        for (int i = 0; i < n; ++i)
            if (i % 3 != n % 3)
                res += A[i];
        return res;
    }

Minimum Cost of Buying Candies With Discount Leetcode Solution in C++

    int minimumCost(vector<int>& A) {
        sort(A.begin(), A.end());
        int res = 0, n = A.size();
        for (int i = 0; i < A.size(); ++i)
            if (i % 3 != n % 3)
                res += A[i];
        return res;
    }

Minimum Cost of Buying Candies With Discount Leetcode Solution in Python

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)
        res, i, N = 0, 0, len(cost)
        while i < N:
            res += sum(cost[i : i + 2])
            i += 3
        return res

Minimum Cost of Buying Candies With Discount Leetcode Solution in Python 3

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        return sum(x for i, x in enumerate(sorted(cost, reverse=True)) if (i+1)%3)

Problem 2 – Count the Hidden Sequences Leetcode Solution

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i].

You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

  • For example, given differences = [1, -3, 4]lower = 1upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).
    • [3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.
    • [5, 6, 3, 7] is not possible since it contains an element greater than 6.
    • [1, 2, 3, 4] is not possible since the differences are not correct.

Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

Example 1:

Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: The possible hidden sequences are:
- [3, 4, 1, 5]
- [4, 5, 2, 6]
Thus, we return 2.

Example 2:

Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4
Explanation: The possible hidden sequences are:
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
Thus, we return 4.

Example 3:

Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0
Explanation: There are no possible hidden sequences. Thus, we return 0.

Constraints:

  • n == differences.length
  • 1 <= n <= 105
  • -105 <= differences[i] <= 105
  • -105 <= lower <= upper <= 105

Count the Hidden Sequences Leetcode Solution in Java

    public int numberOfArrays(int[] diff, int lower, int upper) {
        long a = 0, ma = 0, mi = 0;
        for (int d: diff) {
            a += d;
            ma = Math.max(ma, a);
            mi = Math.min(mi, a);
        }
        return (int)Math.max(0, (upper - lower) - (ma - mi) + 1);
    }

Count the Hidden Sequences Leetcode Solution in C++

    int numberOfArrays(vector<int>& diff, int lower, int upper) {
        long a = 0, ma = 0, mi = 0;
        for (int d: diff) {
            a += d;
            ma = max(ma, a);
            mi = min(mi, a);
        }
        return max(0L, (upper - lower) - (ma - mi) + 1);
    }

Count the Hidden Sequences Leetcode Solution in Python 3

    def numberOfArrays(self, diff, lower, upper):
        A = list(accumulate(diff, initial = 0))
        return max(0, (upper - lower) - (max(A) - min(A)) + 1)

Count the Hidden Sequences Leetcode Solution in Kotlin

    fun numberOfArrays(differences: IntArray, lower: Int, upper: Int): Int {
        var accSum = 0L
        var minSum = 0L
        var maxSum = 0L
        
        for(diff in differences){
            accSum += diff
            minSum = minOf(accSum , minSum)
            maxSum = maxOf(accSum, maxSum)
        }
        
        return maxOf(0, (upper- lower) - (maxSum - minSum) +1).toInt()
    }

Count the Hidden Sequences Leetcode Solution in Python

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
		# Largest Increment
        maxAdd = 0;
		
		# Largest Decrement
        minSub = 0;
		
		# Current Difference
        currDiff = 0;
		
		# Calculating above values in this loop
        for i in range(len(differences)):
            currDiff += differences[i]
			
			# We need largest increment, so we choose the maximum value
            maxAdd = max(currDiff, maxAdd)
			
			# We need largest decrement, so we choose the minimum value
            minSub = min(currDiff, minSub)
        
		# Return 0 if value of the equation is negative
        return max(0, (upper - maxAdd) - (lower - minSub) + 1);
        

Problem 3 – K Highest Ranked Items Within a Price Range Leetcode Solution

You are given a 0-indexed 2D integer array grid of size m x n that represents a map of the items in a shop. The integers in the grid represent the following:

  • 0 represents a wall that you cannot pass through.
  • 1 represents an empty cell that you can freely move to and from.
  • All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.

It takes 1 step to travel between adjacent grid cells.

You are also given integer arrays pricing and start where pricing = [low, high] and start = [row, col] indicates that you start at the position (row, col) and are interested only in items with a price in the range of [low, high] (inclusive). You are further given an integer k.

You are interested in the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different:

  1. Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
  2. Price (lower price has a higher rank, but it must be in the price range).
  3. The row number (smaller row number has a higher rank).
  4. The column number (smaller column number has a higher rank).

Return the k highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.

Example 1:

Input: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
Output: [[0,1],[1,1],[2,1]]
Explanation: You start at (0,0).
With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2).
The ranks of these items are:
- (0,1) with distance 1
- (1,1) with distance 2
- (2,1) with distance 3
- (2,2) with distance 4
Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).

Example 2:

Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
Output: [[2,1],[1,2]]
Explanation: You start at (2,3).
With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1).
The ranks of these items are:
- (2,1) with distance 2, price 2
- (1,2) with distance 2, price 3
- (1,1) with distance 3
- (0,1) with distance 4
Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).

Example 3:

Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
Output: [[2,1],[2,0]]
Explanation: You start at (0,0).
With a price range of [2,3], we can take items from (2,0) and (2,1). 
The ranks of these items are: 
- (2,1) with distance 5
- (2,0) with distance 6
Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). 
Note that k = 3 but there are only 2 reachable items within the price range.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 0 <= grid[i][j] <= 105
  • pricing.length == 2
  • 2 <= low <= high <= 105
  • start.length == 2
  • 0 <= row <= m - 1
  • 0 <= col <= n - 1
  • grid[row][col] > 0
  • 1 <= k <= m * n

K Highest Ranked Items Within a Price Range Leetcode Solution in Python

class Solution:
    def highestRankedKItems(self, G, pricing, start, k):
        m, n = len(G), len(G[0])
        row, col = start
        node = (0, G[row][col], row, col)
        visited = set()
        visited.add((row, col))
        d = deque([node])
        ans = []
        
        while d:
            dist, cost, row, col = d.popleft()
            if pricing[0] <= cost <= pricing[1]:
                ans += [(dist, cost, row, col)]
            
            for x, y in (row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1):
                if 0 <= x <= m-1 and 0 <= y <= n-1 and (x, y) not in visited and G[x][y] != 0:
                    d.append((dist + 1, G[x][y], x, y))
                    visited.add((x, y))
        
        ans = sorted(ans)
        
        return [[x, y] for _, _, x, y in ans[:k]]

K Highest Ranked Items Within a Price Range Leetcode Solution in C++

class Solution {
public:
    vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& price, vector<int>& start, int k) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>>ans,res;
        // visited array
        vector<vector<bool>>seen(m,vector<bool>(n,false));
        // queue for BFS
        queue<pair<int,int>>q;
        q.push({start[0],start[1]});
        //directions
        vector<vector<int>>dirs={{-1,0},{0,-1},{0,1},{1,0}};
        // distance
        int dist=0;
        while(!q.empty()){
            int size=q.size();
            while(size--){
                auto p=q.front();
                    q.pop();
                // already visited cell
                if(seen[p.first][p.second])
                    continue;
                // found wall
                if(grid[p.first][p.second]==0)
                    continue;
                // make the cell visited ,if visiting first time
                seen[p.first][p.second]=true;
                // if the value is 1 then it is empty cell so first check it
                if(grid[p.first][p.second]!=1){
                    int val=grid[p.first][p.second];
                    // cell value should be in the range of price,if yes then push it to array or min-heap
                    if(val>=price[0] && val<=price[1])
                       res.push_back({dist,val,p.first,p.second});
                }
                // check other cells which you can reach from current cell
                for(auto & dir:dirs){
                    int row=p.first+dir[0],col=dir[1]+p.second;
                    if(row>=0 && row<m && col>=0 && col<n)
                        q.push({row,col});
                }      
            }
            dist++;
        }
        // sort the array, if you have used min-heap,then obviously there is no need
        sort(res.begin(),res.end());
        // first k values or whole vector,whatever is minimum
        for(int i=0;i<min(int(k),int(res.size()));i++)
            ans.push_back({res[i][2],res[i][3]});
        return ans;
        
    }
};

K Highest Ranked Items Within a Price Range Leetcode Solution in Java

    private static final int[] d = {0, 1, 0, -1, 0};
    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        int R = grid.length, C = grid[0].length;
        int x = start[0], y = start[1], low = pricing[0], high = pricing[1];
        Set<String> seen = new HashSet<>(); // Set used to prune duplicates.
        seen.add(x + "," + y);
        List<List<Integer>> ans = new ArrayList<>();
        // PriorityQueue sorted by (distance, price, row, col).
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] == b[1] ? a[2] == b[2] ? a[3] - b[3] : a[2] - b[2] : a[1] - b[1] : a[0] - b[0]);
        pq.offer(new int[]{0, grid[x][y], x, y}); // BFS starting point.
        while (!pq.isEmpty() && ans.size() < k) {
            int[] cur = pq.poll();
            int distance = cur[0], price = cur[1], r = cur[2], c = cur[3]; // distance, price, row & column.
            if (low <= price && price <= high) { // price in range?
                ans.add(Arrays.asList(r, c));
            }
            for (int m = 0; m < 4; ++m) { // traverse 4 neighbors.
                int i = r + d[m], j = c + d[m + 1];
                // in boundary, not wall, and not visited yet?
                if (0 <= i && i < R && 0 <= j && j < C && grid[i][j] > 0 && seen.add(i + "," + j)) {
                    pq.offer(new int[]{distance + 1, grid[i][j], i, j});
                }
            }
        }
        return ans;
    }

K Highest Ranked Items Within a Price Range Leetcode Solution in Python

    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        R, C = map(len, (grid, grid[0]))
        ans, (x, y), (low, high) = [], start, pricing
        heap = [(0, grid[x][y], x, y)]
        seen = {(x, y)}
        while heap and len(ans) < k:
            distance, price, r, c = heapq.heappop(heap)
            if low <= price <= high:
                ans.append([r, c])
            for i, j in (r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c):
                if R > i >= 0 <= j < C and grid[i][j] > 0 and (i, j) not in seen: 
                    seen.add((i, j))
                    heapq.heappush(heap, (distance + 1, grid[i][j], i, j))
        return ans

Problem 4 – Number of Ways to Divide a Long Corridor Leetcode Solution

Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters 'S' and 'P' where each 'S' represents a seat and each 'P' represents a plant.

One room divider has already been installed to the left of index 0, and another to the right of index n - 1. Additional room dividers can be installed. For each position between indices i - 1 and i (1 <= i <= n - 1), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.

Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 109 + 7. If there is no way, return 0.

Example 1:

Input: corridor = "SSPPSPS"
Output: 3
Explanation: There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, each section has exactly two seats.

Example 2:

Input: corridor = "PPSPSP"
Output: 1
Explanation: There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.

Example 3:

Input: corridor = "S"
Output: 0
Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.

Constraints:

  • n == corridor.length
  • 1 <= n <= 105
  • corridor[i] is either 'S' or 'P'.

Number of Ways to Divide a Long Corridor Leetcode Solution in C++

    int numberOfWays(string s) {
        long res = 1, j = 0, k = 0, mod = 1e9 + 7;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == 'S') {
                if (++k > 2 && k % 2 == 1)
                    res = res * (i - j) % mod;
                j = i;
            }
        }
        return k % 2 == 0 && k > 0 ? res : 0;
    }

Number of Ways to Divide a Long Corridor Leetcode Solution in Java

    public int numberOfWays(String s) {
        long res = 1, j = 0, k = 0, mod = (long)1e9 + 7;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == 'S') {
                if (++k > 2 && k % 2 == 1)
                    res = res * (i - j) % mod;
                j = i;
            }
        }
        return k % 2 == 0 && k > 0 ? (int)res : 0;
    }

Number of Ways to Divide a Long Corridor Leetcode Solution in Python

    def numberOfWays(self, s):
        a = [i for i,c in enumerate(s) if c == 'S']
        res = 1
        for i in xrange(1,len(a) - 1,2):
            res *= a[i+1] - a[i]
        return res % (10**9+7) * (len(a) % 2 == 0 and len(a) >= 2)     
Biweekly Contest 70 LeetCode Solution Review:

In our experience, we suggest you solve this Biweekly Contest 70 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Biweekly Contest 70 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Biweekly Contest 70 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.