Weekly Contest 273 LeetCode Solution

Problem 1 – A Number After a Double Reversal LeetCode Solution

Reversing an integer means to reverse all its digits.

  • For example, reversing 2021 gives 1202. Reversing 12300 gives 321 as the leading zeros are not retained.

Given an integer numreverse num to get reversed1then reverse reversed1 to get reversed2. Return true if reversed2 equals num. Otherwise return false.

Example 1:

Input: num = 526
Output: true
Explanation: Reverse num to get 625, then reverse 625 to get 526, which equals num.

Example 2:

Input: num = 1800
Output: false
Explanation: Reverse num to get 81, then reverse 81 to get 18, which does not equal num.

Example 3:

Input: num = 0
Output: true
Explanation: Reverse num to get 0, then reverse 0 to get 0, which equals num.

Constraints:

  • 0 <= num <= 106

A Number After a Double Reversal LeetCode Solution in Python

class Solution(object):
    def isSameAfterReversals(self, num):
		# All you have to do is check the Trailing zeros
        return num == 0 or num % 10  # num % 10 means num % 10 != 0

A Number After a Double Reversal LeetCode Solution in C++

class Solution {
public:
    bool isSameAfterReversals(int num) {
        return num == 0 || num % 10 > 0; // All you have to do is check the Trailing zeros
    }
};

A Number After a Double Reversal LeetCode Solution in Java

class Solution {
    public boolean isSameAfterReversals(int num) {
        return num == 0 || num % 10 > 0; // All you have to do is check the Trailing zeros
    }
}

A Number After a Double Reversal LeetCode Solution in Python 3

class Solution:
    def isSameAfterReversals(self, num: int) -> bool:
        return not num or num % 10

A Number After a Double Reversal LeetCode Solution in JavaScript

/**
 * @param {number} num
 * @return {boolean}
 */
var isSameAfterReversals = function(num) {
    if(num == 0)    return true;
    if(num % 10 == 0)   return false;
    return true;
};

Problem 2 – Execution of All Suffix Instructions Staying in a Grid LeetCode Solution

There is an n x n grid, with the top-left cell at (0, 0) and the bottom-right cell at (n - 1, n - 1). You are given the integer n and an integer array startPos where startPos = [startrow, startcol] indicates that a robot is initially at cell (startrow, startcol).

You are also given a 0-indexed string s of length m where s[i] is the ith instruction for the robot: 'L' (move left), 'R' (move right), 'U' (move up), and 'D' (move down).

The robot can begin executing from any ith instruction in s. It executes the instructions one by one towards the end of s but it stops if either of these conditions is met:

  • The next instruction will move the robot off the grid.
  • There are no more instructions left to execute.

Return an array answer of length m where answer[i] is the number of instructions the robot can execute if the robot begins executing from the ith instruction in s.

Example 1:

Input: n = 3, startPos = [0,1], s = "RRDDLU"
Output: [1,5,4,3,1,0]
Explanation: Starting from startPos and beginning execution from the ith instruction:
- 0th: "RRDDLU". Only one instruction "R" can be executed before it moves off the grid.
- 1st:  "RDDLU". All five instructions can be executed while it stays in the grid and ends at (1, 1).
- 2nd:   "DDLU". All four instructions can be executed while it stays in the grid and ends at (1, 0).
- 3rd:    "DLU". All three instructions can be executed while it stays in the grid and ends at (0, 0).
- 4th:     "LU". Only one instruction "L" can be executed before it moves off the grid.
- 5th:      "U". If moving up, it would move off the grid.

Example 2:

Input: n = 2, startPos = [1,1], s = "LURD"
Output: [4,1,0,0]
Explanation:
- 0th: "LURD".
- 1st:  "URD".
- 2nd:   "RD".
- 3rd:    "D".

Example 3:

Input: n = 1, startPos = [0,0], s = "LRUD"
Output: [0,0,0,0]
Explanation: No matter which instruction the robot begins execution from, it would move off the grid.

Constraints:

  • m == s.length
  • 1 <= n, m <= 500
  • startPos.length == 2
  • 0 <= startrow, startcol < n
  • s consists of 'L''R''U', and 'D'.

Execution of All Suffix Instructions Staying in a Grid LeetCode Solution in C++

vector<int> executeInstructions(int n, vector<int>& st, string s) {
    int m = s.size(), h = m + n, v = m + n;
    vector<int> hor((m + n) * 2, m), ver((m + n) * 2, m), res(m);
    for (int i = m - 1; i >= 0; --i) {
        hor[h] = ver[v] = i;
        h += s[i] == 'L' ? 1 : s[i] == 'R' ? -1 : 0;
        v += s[i] == 'U' ? 1 : s[i] == 'D' ? -1 : 0;
        res[i] = min({m, hor[h - st[1] - 1], hor[h - st[1] + n], ver[v - st[0] - 1], ver[v - st[0] + n]}) - i;
    }
    return res;
}    

Execution of All Suffix Instructions Staying in a Grid LeetCode Solution in Python

    def executeInstructions(self, n, start, s):
        na = len(s)
        def test(i):
            res = 0
            x,y = start
            for j in xrange(i, na):
                o = s[j]
                if o == 'L': y -= 1
                if o == 'R': y += 1
                if o == 'U': x -= 1
                if o == 'D': x += 1
                if not (0 <= x < n and 0 <= y < n):
                    return j - i
            return na - i
        return map(test, range(na))

Execution of All Suffix Instructions Staying in a Grid LeetCode Solution in Java

class Solution {
    int fun(int n,int ind,int pos[],char arr[])
    {
        if(ind==arr.length)
            return 0;
        if(arr[ind]=='R'&&pos[1]+1<n)
            return 1+fun(n,ind+1,new int[]{pos[0],pos[1]+1},arr);
        else if(arr[ind]=='L'&&pos[1]-1>=0)
            return 1+fun(n,ind+1,new int[]{pos[0],pos[1]-1},arr);
        else if(arr[ind]=='U'&&pos[0]-1>=0)
            return 1+fun(n,ind+1,new int[]{pos[0]-1,pos[1]},arr);
        else if(arr[ind]=='D'&&pos[0]+1<n)
            return 1+fun(n,ind+1,new int[]{pos[0]+1,pos[1]},arr);
        else
            return 0;
    }
    public int[] executeInstructions(int n, int[] pos, String s) {
        
        int i,j,len=s.length();
        int ans[]=new int[len];
        for(i=0;i<len;i++)
            ans[i]=fun(n,0,pos,s.substring(i,len).toCharArray());
        return ans;
    }
}

Execution of All Suffix Instructions Staying in a Grid LeetCode Solution in Scala


def executeInstructions(n: Int, startPos: Array[Int], s: String): Array[Int] = {
    def help(i: Int):Int ={
      s.substring(i).foldLeft((startPos(0), startPos(1), 0))((acc, cur)=>{
        cur match {
          case 'L' if acc._2 - 1 >= 0 => (acc._1, acc._2 - 1, acc._3 + 1)
          case 'R' if acc._2 + 1 < n  => (acc._1, acc._2 + 1, acc._3 + 1)
          case 'U' if acc._1 - 1 >= 0 => (acc._1 - 1, acc._2, acc._3 + 1)
          case 'D' if acc._1 + 1 < n  => (acc._1 + 1, acc._2, acc._3 + 1)
          case _ => return acc._3
        }
      })._3
    }
    (0 until s.length).map(help(_)).toArray
  }

Problem 3 – Intervals Between Identical Elements LeetCode Solution

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

Constraints:

  • n == arr.length
  • 1 <= n <= 105
  • 1 <= arr[i] <= 105

Intervals Between Identical Elements LeetCode Solution in C++

class Solution {
public:
    vector<long long> getDistances(vector<int>& arr) {
        int size=arr.size();
        vector<long long>pre(size,0),suf(size,0),ans(size,0);
        unordered_map<int,vector<int>>mp;
        
        // store index of the same elements.
        for(int i=0;i<size;i++)
            mp[arr[i]].push_back(i);
       //  prefix will store the sum of absolute diff. from the starting index of current element to the current index.
        // pre[cur index]=pre[prev index]+ number of same elements before cur element * abs diff of cur element pos and pre element pos
        for(auto &p:mp){
            auto vec=p.second;
            for(int i=1;i<vec.size();i++)
                pre[vec[i]]=  pre[vec[i-1]]+  i*(long)(vec[i]-vec[i-1]);
        }
       // suffix will store the sum of absolute diff. from the ending index of current element to the current index.
        // same formula as above but in reverse order
        for(auto &p:mp){
            auto vec=p.second;
            for(int i=vec.size()-2;i>=0;i--)
                suf[vec[i]]=  suf[vec[i+1]] + long(vec.size()-1-i) * (long)(vec[i+1]-vec[i]);
        }
        for(int i=0;i<size;i++)
            ans[i]+=(pre[i]+suf[i]);
        return ans;
    }
};

Intervals Between Identical Elements LeetCode Solution in Java

class Solution {
    public long[] getDistances(int[] arr) {
        long[] output = new long[arr.length];
        Map<Integer, Long> sumMap = new HashMap<>();
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < arr.length; ++ i) {
            if (!sumMap.containsKey(arr[i])) {
                sumMap.put(arr[i], 0l);
                countMap.put(arr[i], 0);
            }
            
            output[i] += i * (long)countMap.get(arr[i]) - sumMap.get(arr[i]);
            sumMap.put(arr[i], sumMap.get(arr[i]) + i);
            countMap.put(arr[i], countMap.get(arr[i]) + 1);
        }
        
        sumMap = new HashMap<>();
        countMap = new HashMap<>();
        int len = arr.length;
        for (int i = len - 1; i >= 0; -- i) {
            if (!sumMap.containsKey(arr[i])) {
                sumMap.put(arr[i], 0l);
                countMap.put(arr[i], 0);
            }
            
            output[i] += (len - i - 1) * (long)countMap.get(arr[i]) - sumMap.get(arr[i]);
            sumMap.put(arr[i], sumMap.get(arr[i]) + (len - i - 1));
            countMap.put(arr[i], countMap.get(arr[i]) + 1);
        }
        
        return output;
    }
}

Intervals Between Identical Elements LeetCode Solution in Python 3

class Solution:
    def getDistances(self, arr: List[int]) -> List[int]:
        loc = defaultdict(list)
        for i, x in enumerate(arr): loc[x].append(i)
        
        for k, idx in loc.items(): 
            prefix = list(accumulate(idx, initial=0))
            vals = []
            for i, x in enumerate(idx): 
                vals.append(prefix[-1] - prefix[i] - prefix[i+1] - (len(idx)-2*i-1)*x)
            loc[k] = deque(vals)
        
        return [loc[x].popleft() for x in arr]

Intervals Between Identical Elements LeetCode Solution in Python


# helper data structure Scout
class Scout:
    
    def __init__(self, prev_idx=-1, count_of_equal=0):
        
        # record of index of last identical element
        self.prev_idx = prev_idx
        
        # count of identical elements so far
        self.count_of_equal = count_of_equal
    
    def __iter__(self):
		# ouput previous index, and count of equal in order
        return iter( (self.prev_idx, self.count_of_equal) )
    
    
        
class Solution:
    def getDistances(self, arr: List[int]) -> List[int]:
        
        size = len(arr)
        
        pre_scout = defaultdict( Scout )
        pre_dist_sum = [0 for _ in range(size)]
        
        post_scout = defaultdict( Scout )
        post_dist_sum = [0 for _ in range(size)]
        
        
        ## Step_1:
        # update for pre_dist_sum table, direction is from left to right
        for i, element in enumerate(arr):
            
            prev_equal_idx, prev_count_of_equal = pre_scout[element]
            
            # update pre_dist_sum table if we have identical elements before index i
            if prev_count_of_equal:
                pre_dist_sum[i] += pre_dist_sum[ prev_equal_idx ] + (i - prev_equal_idx) * prev_count_of_equal
            
            # update Scout information for current element
            pre_scout[element] = i, prev_count_of_equal+1
            
        # --------------------------------------------------------------
        
        ## Step_2:
        # update for pos_dist_sum table, direction is from right to left
        for i, element in reversed( [*enumerate(arr)] ):
            
            post_equal_idx, post_count_of_equal = post_scout[element]

            # update post_dist_sum table if we have identical elements after index i
            if post_count_of_equal:
                post_dist_sum[i] += post_dist_sum[ post_equal_idx ] + (post_equal_idx - i) * post_count_of_equal
            
            # update Scout information for current element
            post_scout[element] = i, post_count_of_equal+1
            
            
        ## Step_3:
        # Generate final output by definition
        return [ pre_dist_sum[i] + post_dist_sum[i] for i in range(size) ]
        
        

Intervals Between Identical Elements LeetCode Solution in JavaScript

var getDistances = function(arr) {
    const map = new Map();
    const result = new Array(arr.length).fill(0);

    for (let i = 0; i < arr.length; i++) {
        const num = arr[i];
        const val = map.get(num) || {
            count: 0,
            sum: 0
        };
        result[i] += (val.count * i) - val.sum;
        val.sum += i;
        val.count++;
        map.set(num, val);
    }
    map.clear();

    for (let i = arr.length - 1; i >= 0; i--) {
        const num = arr[i];
        const val = map.get(num) || {
            count: 0,
            sum: 0
        };
        result[i] += val.sum - (val.count * i);
        val.sum += i;
        val.count++;
        map.set(num, val);
    }

    return result;
};

Problem 4 – Recover the Original Array LeetCode Solution

Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:

  1. lower[i] = arr[i] - k, for every index i where 0 <= i < n
  2. higher[i] = arr[i] + k, for every index i where 0 <= i < n

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.

Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array.

Note: The test cases are generated such that there exists at least one valid array arr.

Example 1:

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12]. 

Example 2:

Input: nums = [1,1,3,3]
Output: [2,2]
Explanation:
If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3].
Combining lower and higher gives us [1,1,3,3], which is equal to nums.
Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0.
This is invalid since k must be positive.

Example 3:

Input: nums = [5,435]
Output: [220]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

Constraints:

  • 2 * n == nums.length
  • 1 <= n <= 1000
  • 1 <= nums[i] <= 109
  • The test cases are generated such that there exists at least one valid array arr.

Recover the Original Array LeetCode Solution in Python

class Solution:
    def recoverArray(self, nums):
        def check(nums, k):
            cnt, ans = Counter(nums), []
            for num in nums:
                if cnt[num] == 0: continue
                if cnt[num + k] == 0: return False, []
                cnt[num] -= 1
                cnt[num + k] -= 1
                ans += [num + k//2]
            return True, ans
            
        nums = sorted(nums)
        n = len(nums)
        for i in range(1, n):
            k = nums[i] - nums[0]
            if k != 0 and k % 2 == 0:
                a, b = check(nums, k)
                if a: return b

Recover the Original Array LeetCode Solution in C++

vector<int> recoverArray(vector<int>& nums) {
    multiset<int> s(begin(nums), end(nums));
    int start = *begin(s);
    for (auto it = next(begin(s)); it != end(s); ++it) {
        int k = (*it - start) / 2;
        if (k > 0 && start + 2 * k == *it) {
            vector<int> res;
            auto ss = s;
            while(!ss.empty()) {
                auto it_h = ss.find(*begin(ss) + 2 * k);
                if (it_h == end(ss))
                    break;
                res.push_back(*begin(ss) + k);
                ss.erase(begin(ss));
                ss.erase(it_h);
            }
            if (ss.empty())
                return res;
        }
    }
    return {};
}

Recover the Original Array LeetCode Solution in Java

class Solution {
    public int[] recoverArray(int[] nums) {
        int N = nums.length;
        Arrays.sort(nums);
        List<Integer> diffList = new ArrayList<>();
        for (int i = 1; i < N; i++) {
            int diff = Math.abs(nums[i] - nums[0]);
            if (diff % 2 == 0 && diff > 0) diffList.add(diff / 2);
        }
        Map<Integer, Integer> map1 = new HashMap<>();
        for (int i = 0; i < N; i++)
            map1.put(nums[i], map1.getOrDefault(nums[i], 0) + 1);
        for (int diff : diffList) {
            Map<Integer, Integer> map = new HashMap<>(map1);
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < N; i++) {
			    if (tmp.size() == N / 2) break;
                int low = nums[i];
                int high = low + 2 * diff;
                if (map.containsKey(low) && map.containsKey(high)) {
                    tmp.add(low + diff);
                    map.put(low, map.get(low) - 1); 
                    map.put(high, map.get(high) - 1);
                    if (map.get(low) == 0) map.remove(low);
                    if (map.get(high) == 0) map.remove(high);
                }
            }
            if (tmp.size() == N / 2) return tmp.stream().mapToInt(i -> i).toArray();
        }
        return null;
    }
}

Recover the Original Array LeetCode Solution in Python 3

class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        cnt = Counter(nums)
        for i in range(1, len(nums)): 
            diff = nums[i] - nums[0]
            if diff and diff&1 == 0: 
                ans = []
                freq = cnt.copy()
                for k, v in freq.items(): 
                    if v: 
                        if freq[k+diff] < v: break 
                        ans.extend([k+diff//2]*v)
                        freq[k+diff] -= v
                else: return ans 
`
Weekly Contest 273 LeetCode Solution Review:

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

Find on LeetCode

Conclusion:

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