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[0];
    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[0]
    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[0];
    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[0];
        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 ndirections[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[12];
		public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
			int[] bob = new int[12];
			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[0] += 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[0] += 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 = [[0] * (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)[0]]
        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

Leave a Reply

Your email address will not be published.