304 North Cardinal St.
Dorchester Center, MA 02124

# 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 `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 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
- We buy candies with costs 5 and 2
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 = 1``upper = 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

# 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

# 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()
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))

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();
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.
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?
}
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:
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