Weekly Contest 283 LeetCode Solution

Problem 1 – Cells in a Range on an Excel Sheet Leetcode Solution

A cell (r, c) of an excel sheet is represented as a string "<col><row>" where:

  • <col> denotes the column number c of the cell. It is represented by alphabetical letters.
    • For example, the 1st column is denoted by 'A', the 2nd by 'B', the 3rd by 'C', and so on.
  • <row> is the row number r of the cell. The rth row is represented by the integer r.

You are given a string s in the format "<col1><row1>:<col2><row2>", where <col1> represents the column c1<row1> represents the row r1<col2> represents the column c2, and <row2> represents the row r2, such that r1 <= r2 and c1 <= c2.

Return the list of cells (x, y) such that r1 <= x <= r2 and c1 <= y <= c2. The cells should be represented as strings in the format mentioned above and be sorted in non-decreasing order first by columns and then by rows.

Example 1:

Input: s = "K1:L2"
Output: ["K1","K2","L1","L2"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrows denote the order in which the cells should be presented.

Example 2:

Input: s = "A1:F1"
Output: ["A1","B1","C1","D1","E1","F1"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrow denotes the order in which the cells should be presented.

Constraints:

  • s.length == 5
  • 'A' <= s[0] <= s[3] <= 'Z'
  • '1' <= s[1] <= s[4] <= '9'
  • s consists of uppercase English letters, digits and ':'.

Cells in a Range on an Excel Sheet Leetcode Solution in Python

class Solution:
    def cellsInRange(self, s: str) -> List[str]:
        return [chr(c) + chr(r) for c in range(ord(s[0]), ord(s[3]) + 1) for r in range(ord(s[1]), ord(s[4]) + 1)]

Cells in a Range on an Excel Sheet Leetcode Solution in C++

vector<string> cellsInRange(string s) {
    vector<string> res;
    for (char c = s[0]; c <= s[3]; ++c)
        for (char r = s[1]; r <= s[4]; ++r)
            res.push_back({c, r});
    return res;
}

Cells in a Range on an Excel Sheet Leetcode Solution in Java

    public List<String> cellsInRange(String s) {
        char c1 = s.charAt(0), c2 = s.charAt(3);
        char r1 = s.charAt(1), r2 = s.charAt(4);
        List<String> cells = new ArrayList<>();
        for (char c = c1; c <= c2; ++c) {
            for (char r = r1; r <= r2; ++r) {
                cells.add("" + c + r);
            }
        }
        return cells;
    }

Cells in a Range on an Excel Sheet Leetcode Solution in Python 3

    def cellsInRange(self, s: str) -> List[str]:
        c1, c2 = ord(s[0]), ord(s[3])
        r1, r2 = int(s[1]), int(s[4])
        return [chr(c) + str(r) for c in range(c1, c2 + 1) for r in range(r1, r2 + 1)]

Cells in a Range on an Excel Sheet Leetcode Solution in JavaScript

const cellsInRange = (s) => {
  const [fromLetter, fromNum, , toLetter, toNum] = s;
  const ret = [];
  for (let l1 = fromLetter.charCodeAt(0), l2 = toLetter.charCodeAt(0); l1 <= l2; ++l1) {
    for (let n1 = +fromNum, n2 = +toNum; n1 <= n2; ++n1) {
      ret.push(String.fromCharCode(l1) + n1);
    }
  }
  return ret;
};

Problem 2 – Append K Integers With Minimal Sum Leetcode Solution

You are given an integer array nums and an integer k. Append k unique positive integers that do not appear in nums to nums such that the resulting total sum is minimum.

Return the sum of the k integers appended to nums.

Example 1:

Input: nums = [1,4,25,10,25], k = 2
Output: 5
Explanation: The two unique positive integers that do not appear in nums which we append are 2 and 3.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.

Example 2:

Input: nums = [5,6], k = 6
Output: 25
Explanation: The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. 
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 108

Append K Integers With Minimal Sum Leetcode Solution in C++

long long minimalKSum(vector<int>& nums, int k) {
    long long res = (long long)k * (k + 1) / 2, last = 0;
    make_heap(begin(nums), end(nums), greater<int>());
    while (!nums.empty() && nums.front() <= k) {
        int n = nums.front();
        pop_heap(begin(nums), end(nums), greater<int>()); nums.pop_back();
        if (n != last) 
            res += (++k) - n;
        last = n;
    }
    return res;
}

Append K Integers With Minimal Sum Leetcode Solution in Python

def minimalKSum(self, A: List[int], k: int) -> int:
        A = sorted(list(set(A)))
        n = len(A)
        
        if A[n - 1] <= k + n:
            return (k + n) * (k + n + 1) // 2 - sum(A)

        lft, rgt = 0, n - 1
        while rgt > lft:
            mid = (lft + rgt) // 2
            if A[mid] - mid <= k:
                lft = mid + 1
            else:
                rgt = mid

        return (k + lft) * (k + lft + 1) // 2 - sum(A[:lft])

Append K Integers With Minimal Sum Leetcode Solution in JavaScript

const minimalKSum = (nums, k) => {
  const set = new Set(nums);
  let sum = (1 + k) * k / 2;
  let more = 0;
  nums = Array.from(set)
  for (const n of nums) {
    n <= k && (++more, sum -= n);
  }
  while (more > 0) {
    !set.has(++k) && (sum += k, --more);
  }
  return sum;
};

Append K Integers With Minimal Sum Leetcode Solution in Java

    public long minimalKSum(int[] nums, int k) {
        Arrays.sort(nums);
        long ans = 0, lo = 1;
        for (int num : nums) {
            if (num > lo) {
                long hi = Math.min(num - 1, lo + k - 1);
                int cnt = (int)(hi - lo + 1);
                ans += (lo + hi) * cnt / 2;
                k -= cnt;
                if (k == 0) {
                    return ans;
                }
            } 
            lo = num + 1;
        }
        if (k > 0) {
            ans += (lo + lo + k - 1) * k / 2;
        }
        return ans;
    }

Append K Integers With Minimal Sum Leetcode Solution in Python 3

    def minimalKSum(self, nums: List[int], k: int) -> int:
        ans, lo = 0, 1
        cnt = 0
        for num in sorted(nums):
            if num > lo:
                hi = min(num - 1, k - 1 + lo)
                cnt = hi - lo + 1
                ans += (lo + hi) * cnt // 2 
                k -= cnt
                if k == 0:
                    return ans
            lo = num + 1
        if k > 0:
            ans += (lo + lo + k - 1) * k // 2
        return ans

Problem 3 – Create Binary Tree From Descriptions Leetcode Solution

You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,

  • If isLefti == 1, then childi is the left child of parenti.
  • If isLefti == 0, then childi is the right child of parenti.

Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

Example 1:

Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.

Example 2:

Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.

Constraints:

  • 1 <= descriptions.length <= 104
  • descriptions[i].length == 3
  • 1 <= parenti, childi <= 105
  • 0 <= isLefti <= 1
  • The binary tree described by descriptions is valid.

Create Binary Tree From Descriptions Leetcode Solution in C++

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions){
        unordered_map<int, TreeNode*> getNode;                          //to check if node alredy exist
        unordered_map<int, bool> isChild;                               //to check if node has parent or not
        for(auto &v: descriptions){
            if(getNode.count(v[0])==0){
                TreeNode* par = new TreeNode(v[0]);
                getNode[v[0]] = par;
            }
            if(getNode.count(v[1])==0){
                TreeNode* child = new TreeNode(v[1]);
                getNode[v[1]] = child;
            }
            if(v[2]==1) getNode[v[0]]->left = getNode[v[1]];               //left-child
            else getNode[v[0]]->right = getNode[v[1]];                     //right-child
            isChild[v[1]] = true;
        }
        TreeNode* ans = NULL;
        for(auto &v: descriptions){
            if(isChild[v[0]] != true){                  //if node has no parent then this is root node
                ans = getNode[v[0]]; 
                break;
            }
        }
        return ans;
    }
};

Create Binary Tree From Descriptions Leetcode Solution in Java

public TreeNode createBinaryTree(int[][] descriptions) {
        HashMap<Integer, TreeNode> map = new HashMap<>();
        Set<Integer> children = new HashSet<>();
        for (int[] arr : descriptions) {
            int parent = arr[0], child = arr[1], isLeft = arr[2];
            children.add(child);
            TreeNode node = map.getOrDefault(parent, new TreeNode(parent));
            if (isLeft == 1) {
                node.left = map.getOrDefault(child, new TreeNode(child));
                map.put(child, node.left);
            } else {
                node.right = map.getOrDefault(child, new TreeNode(child));
                map.put(child, node.right);
            }
            map.put(parent, node);
        }
        
        int root = -1;
        for (int [] arr: descriptions) {
            if (!children.contains(arr[0])) {
                root = arr[0];
                break;
            }
        }
        
        return map.getOrDefault(root, null);
    }

Create Binary Tree From Descriptions Leetcode Solution in Python

    def createBinaryTree(self, descriptions):
        children = set()
        m = {}
        for p,c,l in descriptions:
            np = m.setdefault(p, TreeNode(p))
            nc = m.setdefault(c, TreeNode(c))
            if l:
                np.left = nc
            else:
                np.right = nc
            children.add(c)
        root = (set(m) - set(children)).pop()
        return m[root]

Create Binary Tree From Descriptions Leetcode Solution in Python 3

HashMap

    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        val_to_node, kids = {}, set()
        for parent, kid, left in descriptions:
            kids.add(kid)
            parent_node = val_to_node.setdefault(parent, TreeNode(parent))
            kid_node = val_to_node.setdefault(kid, TreeNode(kid))
            if left == 1:
                parent_node.left = kid_node
            else:
                parent_node.right = kid_node
        return val_to_node[(val_to_node.keys() - kids).pop()]

BFS

    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        g, kids, parents = defaultdict(list), set(), set()
        for parent, kid, left in descriptions:
            kids.add(kid)
            parents.add(parent)
            g[parent].append([kid, left])
        parents.difference_update(kids)
        root = TreeNode(parents.pop())
        dq = deque([root])
        while dq:
            parent = dq.popleft()
            for kid, left in g.pop(parent.val, []): 
                dq.append(TreeNode(kid))
                if left == 1:
                    parent.left = dq[-1]
                else:
                    parent.right = dq[-1]
        return root

Problem 4 – Replace Non-Coprime Numbers in Array Leetcode Solution

You are given an array of integers nums. Perform the following steps:

  1. Find any two adjacent numbers in nums that are non-coprime.
  2. If no such numbers are found, stop the process.
  3. Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
  4. Repeat this process as long as you keep finding two adjacent non-coprime numbers.

Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 108.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

Example 1:

Input: nums = [6,4,3,2,7,6,2]
Output: [12,7,6]
Explanation: 
- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.

Example 2:

Input: nums = [2,2,1,1,3,3,3]
Output: [2,1,1,3]
Explanation: 
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2,1,1,3].
Note that there are other ways to obtain the same resultant array.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • The test cases are generated such that the values in the final array are less than or equal to 108.

Replace Non-Coprime Numbers in Array Leetcode Solution in Java

    public List<Integer> replaceNonCoprimes(int[] A) {
        LinkedList<Integer> res = new LinkedList();
        for (int a : A) {
            while (true) {
                int last = res.isEmpty() ? 1 : res.getLast();
                int x = gcd(last, a);
                if (x == 1) break; // co-prime
                a *= res.removeLast() / x;
            }
            res.add(a);
        }
        return res;
    }

    private int gcd(int a, int b) {
        return b > 0 ? gcd(b, a % b) : a;
    }

Replace Non-Coprime Numbers in Array Leetcode Solution in C++

    vector<int> replaceNonCoprimes(vector<int>& A) {
        vector<int> res;
        for (int a: A) {   
            while (true) {   
                int x = gcd(res.empty() ? 1 : res.back(), a);
                if (x == 1) break; // co-prime
                a *= res.back() / x;
                res.pop_back();
            }
            res.push_back(a);
        }
        return res;
    }

Replace Non-Coprime Numbers in Array Leetcode Solution in Python 3

    def replaceNonCoprimes(self, A):
        res = []
        for a in A:
            while True:
                x = math.gcd(res[-1] if res else 1, a)
                if x == 1: break # co-prime
                a *= res.pop() // x
            res.append(a)
        return res

Replace Non-Coprime Numbers in Array Leetcode Solution in Python

def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
	stk = []
	for num in nums:
		stk.append(num)
		while len(stk) > 1 and gcd(stk[-1], stk[-2]) > 1:
			stk.append(lcm(stk.pop(), stk.pop()))
	return stk

Replace Non-Coprime Numbers in Array Leetcode Solution in JavaScript

function gcd(a, b) {
    while (b > 0) {
        a %= b;
        [a, b] = [b, a];
    }
    return a;
}
function lcm(a, b) {
    return a / gcd(a, b) * b;
}

var replaceNonCoprimes = function(nums) {
    let res = new Array();
    for (let num of nums) {
        while (res.length > 0 && gcd(res.at(-1), num) > 1) {
            num = lcm(res.at(-1), num);
            res.pop();
        }
        res.push(num);
    }
    return res;
};
Weekly Contest 283 LeetCode Solution Review:

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

Find on LeetCode

Conclusion:

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