Weekly Contest 279 LeetCode Solution

Problem 1 – Sort Even and Odd Indices Independently Leetcode Solution

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

  1. Sort the values at odd indices of nums in non-increasing order.
    • For example, if nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.
  2. Sort the values at even indices of nums in non-decreasing order.
    • For example, if nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.

Return the array formed after rearranging the values of nums.

Example 1:

Input: nums = [4,1,2,3]
Output: [2,3,4,1]
Explanation: 
First, we sort the values present at odd indices (1 and 3) in non-increasing order.
So, nums changes from [4,1,2,3] to [4,3,2,1].
Next, we sort the values present at even indices (0 and 2) in non-decreasing order.
So, nums changes from [4,1,2,3] to [2,3,4,1].
Thus, the array formed after rearranging the values is [2,3,4,1].

Example 2:

Input: nums = [2,1]
Output: [2,1]
Explanation: 
Since there is exactly one odd index and one even index, no rearrangement of values takes place.
The resultant array formed is [2,1], which is the same as the initial array. 

Constraints:

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

Sort Even and Odd Indices Independently Leetcode Solution in Python

    def sortEvenOdd(self, A):
        A[::2], A[1::2] = sorted(A[::2]), sorted(A[1::2])[::-1]
        return A

Sort Even and Odd Indices Independently Leetcode Solution in Java

Counting Sort:

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        int[] even = new int[101];
        int[] odd = new int[101];
        int length = nums.length;
        for (int i = 0; i < length; ++i) {
            if (i % 2 == 0) {
                even[nums[i]]++;
            } else {
                odd[nums[i]]++;
            }
        }
        int e = 0;
        int o = 100;
        for (int i = 0; i < length; ++i) {
            if (i % 2 == 0) {
                // check even
                while (even[e] == 0) {
                    ++e;
                }
                nums[i] = e;
                even[e]--;
            } else {
                while(odd[o] == 0) {
                    --o;
                }
                nums[i] = o;
                odd[o]--;
            }
        }
        return nums;
    }
}

Heap:

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        PriorityQueue<Integer> even = new PriorityQueue<>((a, b)->(a - b));
        PriorityQueue<Integer> odd = new PriorityQueue<>((a, b)->(b - a));
        int length = nums.length;
        for (int i = 0; i < length; ++i) {
            if (i % 2 == 0) {
                even.add(nums[i]);
            } else {
                odd.add(nums[i]);
            }
        }
        
        for (int i = 0; i < length; ++i) {
            if (i % 2 == 0) {
                nums[i] = even.poll();
            } else {
                nums[i] = odd.poll();
            }
        }
        return nums;
    }
}

Sort Even and Odd Indices Independently Leetcode Solution in C++

class Solution {
public:
    vector<int> sortEvenOdd(vector<int>& nums) {
        int n = nums.size();
        priority_queue<int> maxheap;
        priority_queue <int, vector<int>, greater<int> > minheap;
        
        // even fill  (0,2,4,6....)
        for(int i=0; i<n;){
            minheap.push(nums[i]);
            i = i+2;
        }
        // odd fill  (1,3,5,7,....)
        for(int i=1; i<n;){
            maxheap.push(nums[i]);
            i = i+2;
        }
        //
        // nums.clear();
        int i = 0;
        while(i<n){
            if(i%2==0){
                nums[i] = minheap.top();
                minheap.pop();
            }
            else{
                nums[i] = maxheap.top();
                maxheap.pop();
            }
            i++;
        }
        return nums;
    }
};

Problem 2 – Smallest Value of the Rearranged Number Leetcode Solution

You are given an integer num. Rearrange the digits of num such that its value is minimized and it does not contain any leading zeros.

Return the rearranged number with minimal value.

Note that the sign of the number does not change after rearranging the digits.

Example 1:

Input: num = 310
Output: 103
Explanation: The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310. 
The arrangement with the smallest value that does not contain any leading zeros is 103.

Example 2:

Input: num = -7605
Output: -7650
Explanation: Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567.
The arrangement with the smallest value that does not contain any leading zeros is -7650.

Constraints:

  • -1015 <= num <= 1015

Smallest Value of the Rearranged Number Leetcode Solution in Python

class Solution:
    def smallestNumber(self, num: int) -> int:
        s = sorted(str(abs(num)), reverse = num < 0)
        non_zero = next((i for i, n in enumerate(s) if n != '0'), 0)
        s[0], s[non_zero] = s[non_zero], s[0]
        return int(''.join(s)) * (1 if num >= 0 else -1)

Smallest Value of the Rearranged Number Leetcode Solution in C++

long long smallestNumber(long long num) {
    auto s = to_string(abs(num));
    sort(begin(s), end(s), [&](int a, int b){ return num < 0 ? a > b : a < b; });
    if (num > 0)
        swap(s[0], s[s.find_first_not_of('0')]);
    return stoll(s) * (num < 0 ? -1 : 1);
}

Smallest Value of the Rearranged Number Leetcode Solution in Java

class Solution {
    public long smallestNumber(long num) {
        if(num == 0){
            return 0;
        }
        boolean isNegative = num < 0;
        num  = num < 0 ? num * -1 : num;
        
        char[] c = String.valueOf(num).toCharArray();
        Arrays.sort(c);
        String str;
        if(!isNegative){
            int non = 0;
			//if not negative we need to find out the first non-leading zero then swap with first zero
            for(; non < c.length; non++){
                if(c[non] != '0'){
                    break;
                }
            }
            char temp = c[non];
            c[non] = c[0];
            c[0] = temp;
            str = new String(c);
        }else{
            str = new String(c);
            StringBuilder sb = new StringBuilder(str);
            str = "-".concat(sb.reverse().toString());
        }
        return Long.valueOf(str);
    }
}

Smallest Value of the Rearranged Number Leetcode Solution in JavaScript

var smallestNumber = function(num) {
    let arr = Array.from(String(num));
    if(num>0){
    arr.sort((a,b)=>{
         return a-b;
    })
    }
    else{
         arr.sort((a,b)=>{
              return b-a;
         })
    }
    for(let i=0;i<arr.length;i++){
       if(arr[i]!=0){
            [arr[0],arr[i]]=[arr[i],arr[0]];
            break;
       }
  }
    return arr.join("");
};

Problem 3 – Design Bitset Leetcode Solution

Bitset is a data structure that compactly stores bits.

Implement the Bitset class:

  • Bitset(int size) Initializes the Bitset with size bits, all of which are 0.
  • void fix(int idx) Updates the value of the bit at the index idx to 1. If the value was already 1, no change occurs.
  • void unfix(int idx) Updates the value of the bit at the index idx to 0. If the value was already 0, no change occurs.
  • void flip() Flips the values of each bit in the Bitset. In other words, all bits with value 0 will now have value 1 and vice versa.
  • boolean all() Checks if the value of each bit in the Bitset is 1. Returns true if it satisfies the condition, false otherwise.
  • boolean one() Checks if there is at least one bit in the Bitset with value 1. Returns true if it satisfies the condition, false otherwise.
  • int count() Returns the total number of bits in the Bitset which have value 1.
  • String toString() Returns the current composition of the Bitset. Note that in the resultant string, the character at the ith index should coincide with the value at the ith bit of the Bitset.

Example 1:

Input
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
Output
[null, null, null, null, false, null, null, true, null, 2, "01010"]

Explanation
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // the value at idx = 3 is updated to 1, so bitset = "00010".
bs.fix(1);     // the value at idx = 1 is updated to 1, so bitset = "01010". 
bs.flip();     // the value of each bit is flipped, so bitset = "10101". 
bs.all();      // return False, as not all values of the bitset are 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "00101".
bs.flip();     // the value of each bit is flipped, so bitset = "11010". 
bs.one();      // return True, as there is at least 1 index with value 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "01010".
bs.count();    // return 2, as there are 2 bits with value 1.
bs.toString(); // return "01010", which is the composition of bitset.

Constraints:

  • 1 <= size <= 105
  • 0 <= idx <= size - 1
  • At most 105 calls will be made in total to fixunfixflipallonecount, and toString.
  • At least one call will be made to allonecount, or toString.
  • At most 5 calls will be made to toString.

Design Bitset Leetcode Solution in Java

class Bitset {
    int size;
    Set<Integer> one = new HashSet<>();
    Set<Integer> zero = new HashSet<>();
    public Bitset(int size) {
        this.size = size;
        for(int i=0;i<size;i++) zero.add(i);
    }
    
    public void fix(int idx) {
        one.add(idx);
        zero.remove(idx);
    }
    
    public void unfix(int idx) {
        one.remove(idx);
        zero.add(idx);
    }
    
	//swapping object's referrence is O(1)
    public void flip() {
        Set<Integer> s = one;
        one = zero;
        zero = s;
    }
    
    public boolean all() {
        return one.size() == size;
    }
    
    public boolean one() {
        return one.size()>=1;
    }
    
    public int count() {
        return one.size();
    }
    
    public String toString() {
        StringBuilder sb=  new StringBuilder();
        for(int i=0;i<size;i++) {
            if(one.contains(i)) sb.append("1"); 
            else if(zero.contains(i)) sb.append("0");
        }
        return sb.toString();
    }
}

Design Bitset Leetcode Solution in C++

    int a = 0, sz = 0, cnt = 0, isFlip = 0;
    string s;
    Bitset(int size) {
        sz = size;
        s = string(sz, '0');
    }
    
    void fix(int idx) {
        if (s[idx] == '0' + isFlip) {
            s[idx] = '1' + '0' - s[idx];
            cnt++;
        }
    }
    
    void unfix(int idx) {
        if (s[idx] == '1' - isFlip) {
            s[idx] = '1' + '0' - s[idx];
            cnt--;
        }
    }
    
    void flip() {
        isFlip ^= 1;
        cnt = sz - cnt;
    }
    
    bool all() {
        return cnt == sz;
    }
    
    bool one() {
        return cnt > 0;
    }
    
    int count() {
        return cnt;
    }
    
    string toString() {
        if (isFlip) {
            string s2 = s;
            for (auto& c: s2)
                c = '0' + '1' - c;
            return s2;
        }
        return s;
    }

Design Bitset Leetcode Solution in Python

class Bitset(object):

    def __init__(self, size):
        self.a = 0
        self.size = size
        self.cnt = 0

    def fix(self, idx):
        if self.a & (1 << idx) == 0:
            self.a |= 1 << idx
            self.cnt += 1

    def unfix(self, idx):
        if self.a & (1 << idx):
            self.a ^= 1 << idx
            self.cnt -= 1

    def flip(self):
        self.a ^= (1 << self.size) - 1
        self.cnt = self.size - self.cnt

    def all(self):
        return self.cnt == self.size

    def one(self):
        return self.a > 0

    def count(self):
        return self.cnt

    def toString(self):
        a = bin(self.a)[2:]
        return a[::-1] + '0' * (self.size - len(a))

Design Bitset Leetcode Solution in Python 3

    def __init__(self, size: int):
        self.sz = size
        self.bits = [False] * size
        self.flipped = [True] * size
        self.bitCount = 0
        
    def fix(self, idx: int) -> None:
        if not self.bits[idx]:
            self.bits[idx] ^= True
            self.flipped[idx] ^= True
            self.bitCount += 1

    def unfix(self, idx: int) -> None:
        if self.bits[idx]:
            self.bits[idx] ^= True
            self.flipped[idx] ^= True
            self.bitCount -= 1

    def flip(self) -> None:
        self.bits, self.flipped = self.flipped, self.bits
        self.bitCount = self.sz - self.bitCount    

    def all(self) -> bool:
        return self.sz == self.bitCount

    def one(self) -> bool:
        return self.bitCount > 0

    def count(self) -> int:
        return self.bitCount

    def toString(self) -> str:
        return ''.join(['1' if b else '0' for b in self.bits])

Problem 4 – Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution

You are given a 0-indexed binary string s which represents a sequence of train cars. s[i] = '0' denotes that the ith car does not contain illegal goods and s[i] = '1' denotes that the ith car does contain illegal goods.

As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations any number of times:

  1. Remove a train car from the left end (i.e., remove s[0]) which takes 1 unit of time.
  2. Remove a train car from the right end (i.e., remove s[s.length - 1]) which takes 1 unit of time.
  3. Remove a train car from anywhere in the sequence which takes 2 units of time.

Return the minimum time to remove all the cars containing illegal goods.

Note that an empty sequence of cars is considered to have no cars containing illegal goods.

Example 1:

Input: s = "1100101"
Output: 5
Explanation: 
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end. Time taken is 1.
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2 + 1 + 2 = 5. 

An alternative way is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
This also obtains a total time of 2 + 3 = 5.

5 is the minimum time taken to remove all the cars containing illegal goods. 
There are no other ways to remove them with less time.

Example 2:

Input: s = "0010"
Output: 2
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
This obtains a total time of 3.

Another way to remove all the cars containing illegal goods from the sequence is to
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2.

Another way to remove all the cars containing illegal goods from the sequence is to 
- remove a car from the right end 2 times. Time taken is 2 * 1 = 2. 
This obtains a total time of 2.

2 is the minimum time taken to remove all the cars containing illegal goods. 
There are no other ways to remove them with less time.

Constraints:

  • 1 <= s.length <= 2 * 105
  • s[i] is either '0' or '1'.

Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in

    public int minimumTime(String s) {
        int n = s.length(), left = 0, res = n;
        for (int i = 0; i < n; ++i) {   
            left = Math.min(left + (s.charAt(i) - '0') * 2, i + 1);
            res = Math.min(res, left + n - 1 - i);
        }
        return res;
    }

Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in C++

    int minimumTime(string s) {
        int n = s.size(), left = 0, res = n;
        for (int i = 0; i < n; ++i) {   
            left = min(left + (s[i] - '0') * 2, i + 1);
            res = min(res, left + n - 1 - i);
        }
        return res;
    }

Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in Python

    def minimumTime(self, s):
        left, res, n = 0, len(s), len(s)
        for i,c in enumerate(s):
            left = min(left + (c == '1') * 2, i + 1)
            res = min(res, left + n - 1 - i)
        return res
Weekly Contest 279 LeetCode Solution Review:

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

Find on LeetCode

Conclusion:

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