304 North Cardinal St.
Dorchester Center, MA 02124

# Weekly Contest 285 LeetCode Solution

## Problem 1 – Count Hills and Valleys in an Array Leetcode Solution

You are given a 0-indexed integer array `nums`. An index `i` is part of a hill in `nums` if the closest non-equal neighbors of `i` are smaller than `nums[i]`. Similarly, an index `i` is part of a valley in `nums` if the closest non-equal neighbors of `i` are larger than `nums[i]`. Adjacent indices `i` and `j` are part of the same hill or valley if `nums[i] == nums[j]`.

Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.

Return the number of hills and valleys in `nums`.

Example 1:

``````Input: nums = [2,4,1,1,6,5]
Output: 3
Explanation:
At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.
At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.
At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.
At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.
At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.
At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley.
There are 3 hills and valleys so we return 3.
``````

Example 2:

``````Input: nums = [6,6,5,5,4,1]
Output: 0
Explanation:
At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley.
At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley.
At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley.
At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley.
At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley.
At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley.
There are 0 hills and valleys so we return 0.
``````

Constraints:

• `3 <= nums.length <= 100`
• `1 <= nums[i] <= 100`

### Count Hills and Valleys in an Array Leetcode Solution in C++

``````int countHillValley(vector<int>& ns) {
//Step 1
std::vector<int> nums;
int l = ns;
nums.push_back(l);
for (int n : ns) {
if (n != l) {
nums.push_back(n);
l = n;
}
}

//Step 2.
int ret = 0;
for (int i = 1; i < nums.size() - 1; i++) {
if (nums[i-1] < nums[i] == nums[i+1] < nums[i]) ret++;
}
return ret;
}
``````

### Count Hills and Valleys in an Array Leetcode Solution in Python

``````def countHillValley(self, ns: List[int]) -> int:
#Step 1
nums = []
l = ns
nums.append(l)
for n in ns:
if n != l:
nums.append(n)
l = n

#Step 2
ret = 0
for i in range (1, len(nums) - 1):
if ((nums[i-1] < nums[i]) == (nums[i+1] < nums[i])):
ret += 1

return ret
``````

### Count Hills and Valleys in an Array Leetcode Solution in JavaScript

``````var countHillValley = function(ns) {
//Step 1
nums = [];
let l = ns;
nums.push(l);
for (let i = 0; i < ns.length; i++) {
n = ns[i];
if (n != l) {
l = n;
nums.push(n);
}
}

//Step 2
let ret = 0;
for (let i = 1; i < nums.length - 1; i++) {
if (nums[i-1] < nums[i] == nums[i+1] < nums[i]) ret++;
}

return ret;
};
``````

### Count Hills and Valleys in an Array Leetcode Solution in Python3

``````class Solution:
def countHillValley(self, nums: List[int]) -> int:
res = 0
candidate = last_num = None

for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
if candidate and ((candidate > last_num and candidate > nums[i]) or (candidate < last_num and candidate < nums[i])):
res += 1
candidate = nums[i]
last_num = nums[i-1]

return res
``````

### Count Hills and Valleys in an Array Leetcode Solution in Java

`````` public int countHillValley(int[] a){
int r = 0, left = a;
for(int i = 1; i < a.length - 1; i++)
if(left < a[i] && a[i] > a[i + 1] || left > a[i] && a[i] < a[i + 1]){
r++;
left = a[i];
}
return r;
}
``````

## Problem 2 – Count Collisions on a Road Leetcode Solution

There are `n` cars on an infinitely long road. The cars are numbered from `0` to `n - 1` from left to right and each car is present at a unique point.

You are given a 0-indexed string `directions` of length `n``directions[i]` can be either `'L'``'R'`, or `'S'` denoting whether the `ith` car is moving towards the left, towards the right, or staying at its current point respectively. Each moving car has the same speed.

The number of collisions can be calculated as follows:

• When two cars moving in opposite directions collide with each other, the number of collisions increases by `2`.
• When a moving car collides with a stationary car, the number of collisions increases by `1`.

After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.

Return the total number of collisions that will happen on the road.

Example 1:

``````Input: directions = "RLRSLL"
Output: 5
Explanation:
The collisions that will happen on the road are:
- Cars 0 and 1 will collide with each other. Since they are moving in opposite directions, the number of collisions becomes 0 + 2 = 2.
- Cars 2 and 3 will collide with each other. Since car 3 is stationary, the number of collisions becomes 2 + 1 = 3.
- Cars 3 and 4 will collide with each other. Since car 3 is stationary, the number of collisions becomes 3 + 1 = 4.
- Cars 4 and 5 will collide with each other. After car 4 collides with car 3, it will stay at the point of collision and get hit by car 5. The number of collisions becomes 4 + 1 = 5.
Thus, the total number of collisions that will happen on the road is 5.
``````

Example 2:

``````Input: directions = "LLRR"
Output: 0
Explanation:
No cars will collide with each other. Thus, the total number of collisions that will happen on the road is 0.
``````

Constraints:

• `1 <= directions.length <= 105`
• `directions[i]` is either `'L'``'R'`, or `'S'`.

### Count Collisions on a Road Leetcode Solution in C++

``````class Solution {
public:
int countCollisions(string dir) {

int res(0), n(size(dir)), i(0), carsFromRight(0);

while (i < n and dir[i] == 'L') i++; // skipping all the cars going to left from beginning as they will never collide

for ( ; i<n; i++) {
if (dir[i] == 'R')  carsFromRight++;
else {
// if dir[i] == 'S' then there will be carsFromRight number of collission
// if dir[i] == 'L' then there will be carsFromRight+1 number of collision (one collision for the rightmost cars and carsFromRight collision for the cars coming from left)
res += (dir[i] == 'S') ? carsFromRight : carsFromRight+1;
carsFromRight = 0;
}
}
return res;
}
};
``````

### Count Collisions on a Road Leetcode Solution in Java

``````class Solution {
public int countCollisions(String dir) {

int res = 0, n = dir.length(), i = 0, carsFromRight = 0;

while (i < n && dir.charAt(i) == 'L') i++;

for ( ; i<n; i++) {
if (dir.charAt(i) == 'R')  carsFromRight++;
else {
res += (dir.charAt(i) == 'S') ? carsFromRight : carsFromRight+1;
carsFromRight = 0;
}
}
return res;
}
}
``````

### Count Collisions on a Road Leetcode Solution in Python

``````class Solution:
def countCollisions(self, directions: str) -> int:
return sum(d!='S' for d in directions.lstrip('L').rstrip('R'))
``````

#### Problem 3 – Maximum Points in an Archery Competition Leetcode Solution

Alice and Bob are opponents in an archery competition. The competition has set the following rules:

1. Alice first shoots `numArrows` arrows and then Bob shoots `numArrows` arrows.
2. The points are then calculated as follows:
1. The target has integer scoring sections ranging from `0` to `11` inclusive.
2. For each section of the target with score `k` (in between `0` to `11`), say Alice and Bob have shot `ak` and `bk` arrows on that section respectively. If `ak >= bk`, then Alice takes `k` points. If `ak < bk`, then Bob takes `k` points.
3. However, if `ak == bk == 0`, then nobody takes `k` points.
• For example, if Alice and Bob both shot `2` arrows on the section with score `11`, then Alice takes `11` points. On the other hand, if Alice shot `0` arrows on the section with score `11` and Bob shot `2` arrows on that same section, then Bob takes `11` points.

You are given the integer `numArrows` and an integer array `aliceArrows` of size `12`, which represents the number of arrows Alice shot on each scoring section from `0` to `11`. Now, Bob wants to maximize the total number of points he can obtain.

Return the array `bobArrows` which represents the number of arrows Bob shot on each scoring section from `0` to `11`. The sum of the values in `bobArrows` should equal `numArrows`.

If there are multiple ways for Bob to earn the maximum total points, return any one of them.

Example 1:

``````Input: numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
Output: [0,0,0,0,1,1,0,0,1,2,3,1]
Explanation: The table above shows how the competition is scored.
Bob earns a total point of 4 + 5 + 8 + 9 + 10 + 11 = 47.
It can be shown that Bob cannot obtain a score higher than 47 points.
``````

Example 2:

``````Input: numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
Output: [0,0,0,0,0,0,0,0,1,1,1,0]
Explanation: The table above shows how the competition is scored.
Bob earns a total point of 8 + 9 + 10 = 27.
It can be shown that Bob cannot obtain a score higher than 27 points.``````

Constraints:

• `1 <= numArrows <= 105`
• `aliceArrows.length == bobArrows.length == 12`
• `0 <= aliceArrows[i], bobArrows[i] <= numArrows`
• `sum(aliceArrows[i]) == numArrows`

### Maximum Points in an Archery Competition Leetcode Solution in Java

``````   class Solution {
int bobPoint = 0;
int[] maxbob = new int;
public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
int[] bob = new int;
calculate(aliceArrows, bob, 11, numArrows, 0);  //Start with max point that is 11
return maxbob;
}
public void calculate(int[] alice, int[] bob, int index, int remainArr, int point) {
if(index < 0 || remainArr <= 0) {
if(remainArr > 0)
bob += remainArr;
if(point > bobPoint) { // Update the max points and result output
bobPoint = point;
maxbob = bob.clone();
}
return;
}
//part 1: assign 1 more arrow than alice
if(remainArr >= alice[index]+1) {
bob[index] = alice[index] + 1;
calculate(alice, bob, index-1, remainArr-(alice[index]+1), point + index);
bob[index] = 0;
}
//part 2: assign no arrow and move to next point
calculate(alice, bob, index-1, remainArr, point);
bob[index] = 0;
}
}
``````

### Maximum Points in an Archery Competition Leetcode Solution in C++

``````class Solution
{
public:
vector<int> ans;
int target = 0;
vector<int> maximumBobPoints(int numArrows, vector<int> &aliceArrows)
{
vector<int> res(12, 0);
rec(11, numArrows, aliceArrows, 0, res);
return ans;
}
void rec(int n, int numArrows, vector<int> &aliceArrow, int sum, vector<int> res)
{
if (n == -1 || numArrows <= 0)
{
if (sum > target)
{
target = sum;
if (numArrows > 0)
{
res += numArrows;
}
ans = res;
}
return;
}
int req = aliceArrow[n] + 1;
if (req <= numArrows)
{
res[n] = req;
rec(n - 1, numArrows - req, aliceArrow, sum + n, res);
res[n] = 0;
}
rec(n - 1, numArrows, aliceArrow, sum, res);
return;
}
};
``````

### Maximum Points in an Archery Competition Leetcode Solution in Python

``````class Solution:
def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
dp = [ * (numArrows + 1) for _ in range(12)]
for i in range(12):
for j in range(1, numArrows + 1):
if i > 0:
dp[i][j] = dp[i-1][j]
if j > aliceArrows[i]:
dp[i][j] = max(dp[i][j], i + dp[i-1][j-aliceArrows[i]-1])
res = []
t = 0
for i in range(11, 0, -1):
if dp[i][numArrows-t] == dp[i-1][numArrows-t]:
res.append(0)
else:
res.append(aliceArrows[i] + 1)
t += aliceArrows[i] + 1
res.append(numArrows - t)
return res[::-1]
``````

## Problem 4 – Longest Substring of One Repeating Character Leetcode Solution

You are given a 0-indexed string `s`. You are also given a 0-indexed string `queryCharacters` of length `k` and a 0-indexed array of integer indices `queryIndices` of length `k`, both of which are used to describe `k` queries.

The `ith` query updates the character in `s` at index `queryIndices[i]` to the character `queryCharacters[i]`.

Return an array `lengths` of length `k` where `lengths[i]` is the length of the longest substring of `s` consisting of only one repeating character after the `ith` query is performed.

Example 1:

``````Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
Output: [3,3,4]
Explanation:
- 1st query updates s = "bbbacc". The longest substring consisting of one repeating character is "bbb" with length 3.
- 2nd query updates s = "bbbccc".
The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3.
- 3rd query updates s = "bbbbcc". The longest substring consisting of one repeating character is "bbbb" with length 4.
Thus, we return [3,3,4].
``````

Example 2:

``````Input: s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
Output: [2,3]
Explanation:
- 1st query updates s = "abazz". The longest substring consisting of one repeating character is "zz" with length 2.
- 2nd query updates s = "aaazz". The longest substring consisting of one repeating character is "aaa" with length 3.
Thus, we return [2,3].
``````

Constraints:

• `1 <= s.length <= 105`
• `s` consists of lowercase English letters.
• `k == queryCharacters.length == queryIndices.length`
• `1 <= k <= 105`
• `queryCharacters` consists of lowercase English letters.
• `0 <= queryIndices[i] < s.length`

### Longest Substring of One Repeating Character Leetcode Solution in C++

``````class sgtree{
public:
vector<int> nums,left,right;
vector<char> lc,rc; int n;
sgtree(string &s){
n = s.size();
nums = vector<int>(4*n+5,0);
left = vector<int>(4*n+5,-1);
right = vector<int>(4*n+5,-1);
lc = vector<char>(4*n+5,'*');
rc = vector<char>(4*n+5,'*');
build(0,s,0,n-1);
}
void build(int in, string &s,int l,int h){
if(l>h) return;
if(l==h){
lc[in] = rc[in] = s[l];
left[in] = l,right[in] = l; nums[in] = 1;
return;
}
int m = (l+h)/2;
build(2*in+1,s,l,m); build(2*in+2,s,m+1,h);
merge(in,l,m,h);
}
void merge(int in,int l,int m,int h){
int lt = in*2+1, rt = in*2+2, max_ = 0;
lc[in] = lc[lt]; rc[in] = rc[rt];
left[in] = left[lt];
right[in] = right[rt];
if(rc[lt]==lc[rt]){
if(left[lt]==m) left[in] = left[rt];
}
if(lc[rt]==rc[lt]){
if(right[rt]==m+1) right[in] = right[lt];
}
if(rc[lt]==lc[rt]) max_ = left[rt]-right[lt]+1;

max_ = max(max_,left[in]-l+1);
max_ = max(max_,h-right[in]+1);
nums[in] = max(max_,max(nums[lt],nums[rt]));
}
int update(int in,int l,int h,int j,char ch){
if(l>h) return 0;
if(l==h){
lc[in] = rc[in] = ch;
left[in] = l,right[in] = l; nums[in] = 1;
return 1;
}
int m = (l+h)/2;
if(j>=l && j<=m) update(2*in+1,l,m,j,ch);
else update(2*in+2,m+1,h,j,ch);
merge(in,l,m,h);
return nums[in];
}
};
class Solution {
public:
vector<int> longestRepeating(string s, string q, vector<int>& in) {
sgtree node(s);
vector<int> re(q.size(),0);
for(int i = 0; i<q.size();++i){
re[i] = node.update(0,0,s.size()-1,in[i],q[i]);
}
return re;
}
};
``````

### Longest Substring of One Repeating Character Leetcode Solution in Java

``````    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
char[] arr = s.toCharArray();
int m = arr.length, n = queryIndices.length;
int[] output = new int[n];
TreeMap<Integer, Integer> lengths = new TreeMap<>(), spans = new TreeMap<>();
// Stores spans of each letter in the TreeMap
for (int i = 0, j = 1; j <= m; j++) if (j == m || arr[i] != arr[j]) {
lengths.put(j - i, lengths.getOrDefault(j - i, 0) + 1);
spans.put(i, j - 1);
i = j;
}
// Update spans on each query and find the max length
for (int i = 0; i < queryIndices.length; i++) {
int j = queryIndices[i];
if (arr[j] != queryCharacters.charAt(i)) {
// Remove the spans that has the character to be updated
int l = spans.floorKey(j), r = spans.remove(l), length = r - l + 1;
if (lengths.get(length) == 1) lengths.remove(length);
else lengths.put(length, lengths.get(length) - 1);
// if the character is going to be different from its neighbors, break the span
if (l < j) {
spans.put(l, j - 1);
lengths.put(j - l, lengths.getOrDefault(j - l, 0) + 1);
}
if (r > j) {
spans.put(j + 1, r);
lengths.put(r - j, lengths.getOrDefault(r - j, 0) + 1);
}
arr[j] = queryCharacters.charAt(i);
l = j;
r = j;
// if the character is going to be same as its neighbors, merge the spans
if (j > 0 && arr[j] == arr[j - 1]) {
l = spans.floorKey(j);
length = spans.remove(l) - l + 1;
if (lengths.get(length) == 1) lengths.remove(length);
else lengths.put(length, lengths.get(length) - 1);
}
if (j < m - 1 && arr[j] == arr[j + 1]) {
int key = spans.ceilingKey(j);
r = spans.remove(key);
length = r - key + 1;
if (lengths.get(length) == 1) lengths.remove(length);
else lengths.put(length, lengths.get(length) - 1);
}
spans.put(l, r);
lengths.put(r - l + 1, lengths.getOrDefault(r - l + 1, 0) + 1);
}
output[i] = lengths.lastKey();
}
return output;
}
``````

### Longest Substring of One Repeating Character Leetcode Solution in Python

``````class SegmentTree:
def __init__(self, n, arr):
self.size = 1
ZERO = (0, 0, 0, 0, 0, 0)
while self.size < n:
self.size *= 2
self.T = [ZERO] * (2 * self.size - 1)
self.arr = arr
self.ZERO = ZERO  # neutral element

def combine(self, a, b):
f1, s1, e1, L1, r1, l1 = a
f2, s2, e2, L2, r2, l2 = b
f = max(f1, f2)
if r1 == l2: f = max(f, e1 + s2)
e = e2 + e1 if (e2 == L2 and r1 == l2) else e2
s = s1 + s2 if (e1 == L1 and r1 == l2) else s1
L = L1 + L2
r = r2
l = l1
return (f, s, e, L, r, l)

def one_element(self, x):
return 1, 1, 1, 1, x, x

def _build(self, x, lx, rx):
if rx - lx == 1:
if lx < len(self.arr):
self.T[x] = self.one_element(self.arr[lx])
else:
mx = (lx + rx) // 2
self._build(2 * x + 1, lx, mx)
self._build(2 * x + 2, mx, rx)
self.T[x] = self.combine(self.T[2 * x + 1], self.T[2 * x + 2])

def build(self):
self._build(0, 0, self.size)

def _set(self, i, v, x, lx, rx):
if rx - lx == 1:
self.T[x] = self.one_element(v)
return
mx = (lx + rx) // 2
if i < mx:
self._set(i, v, 2 * x + 1, lx, mx)
else:
self._set(i, v, 2 * x + 2, mx, rx)
self.T[x] = self.combine(self.T[2 * x + 1], self.T[2 * x + 2])

def set(self, i, v):
self._set(i, v, 0, 0, self.size)

def _calc(self, l, r, x, lx, rx):
if l >= rx or lx >= r:
return self.ZERO
if lx >= l and rx <= r:
return self.T[x]
mx = (lx + rx) // 2
s1 = self._calc(l, r, 2 * x + 1, lx, mx)
s2 = self._calc(l, r, 2 * x + 2, mx, rx)
return self.combine(s1, s2)

def calc(self, l, r):
return self._calc(l, r, 0, 0, self.size)

class Solution:
def longestRepeating(self, s, Q1, Q2):
n = len(s)
m = len(Q1)
ans = []
STree = SegmentTree(n, s)
STree.build()
for i in range(m):
STree.set(Q2[i], Q1[i])
ans += [STree.calc(0, n)]
return ans
``````
##### Weekly Contest 285 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 285 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 Weekly Contest 285 LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Weekly Contest 285 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