Leetcode 2038. Remove Colored Pieces : NileshBlog.Tech

Leetcode 2038. Remove Colored Pieces if Both Neighbors are the Same Color:Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Remove Colored Pieces if Both Neighbors are the Same Color ” or “LeetCode .2038‘

Table of Contents

Greedy Appraoch : Leetcode 2038. Remove Colored Pieces if Both Neighbors are the Same Color

Initialize an vector / array cnts to keep track of the points collected by both players. Initially, both players have zero points.
Initialize currrent to the first color in the string, and count to zero to keep track of the consecutive balls of the current color.

Iterate through the string of colors:
- If the current ball has the same color as the previous one, increment count.
- If count reaches or exceeds 3, update the score in the cnts array for the current player (‘A’ or ‘B’).
- If the current ball has a different color, reset cur to the new color and reset count to 1.
After processing the entire string, the function returns true if player ‘A’ (represented by cnts[0]) has more points than player ‘B’ (represented by cnts[1]), indicating that player ‘A’ is the winner.

DRY and RUN

codes :Leetcode 2038

c++ : Leet code 2038

class Solution {
public:
    bool winnerOfGame(string colors) {
        vector<int> cnts(2, 0);  // Initialize a vector with two elements, both set to 0
        char current = colors[0];
        int count = 0;

        for (const auto &c : colors) {
            if (c == current) {
                if (++count >= 3) cnts[c - 'A']++;
            } else {
                current = c;
                count = 1;
            }
        }

        return cnts[0] > cnts[1];
    }
};

Java: Leet code 2038

public class Solution {
    public boolean winnerOfGame(String colors) {
        int[] cnts = new int[2];
        char current = colors.charAt(0);
        int count = 0;

        for (char c : colors.toCharArray()) {
            if (c == current) {
                if (++count >= 3)
                    cnts[c - 'A']++;
            } else {
                current= c;
                count = 1;
            }
        }

        return cnts[0] > cnts[1];
    }
}

Python: Leet code 2038

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        cnts = [0, 0]
        current= colors[0]
        count = 0

        for c in colors:
            if c == current:
                count += 1
                if count >= 3:
                    cnts[ord(c) - ord('A')] += 1
            else:
                current = c
                count = 1

        return cnts[0] > cnts[1]

JavaScript: Leet code 2038

class Solution {
    winnerOfGame(colors) {
        const cnts = [0, 0];
        let current = colors[0];
        let count = 0;

        for (const c of colors) {
            if (c === current) {
                count++;
                if (count >= 3) {
                    cnts[c.charCodeAt(0) - 'A'.charCodeAt(0)]++;
                }
            } else {
                current= c;
                count = 1;
            }
        }

        return cnts[0] > cnts[1];
    }
}

Boyer-Moore Majority Voting Appraoch

Initialization: In all four programming languages, we start by initializing variables for two potential majority candidates and their counts.

Candidate Selection:
- We loop through the given ‘nums’ array and update the candidates and their counts as follows:
  - If the current number matches ‘candidate1’, we increment ‘count1’.
  - If it matches ‘candidate2’, we increment ‘count2’.
  - If ‘count1’ becomes 0, we update ‘candidate1’ to the current number and set ‘count1’ to 1.
  - If ‘count2’ becomes 0, we update ‘candidate2’ to the current number and set ‘count2’ to 1.
  - Otherwise, we decrement ‘count1’ and ‘count2’.
Counting Occurrences:
- We reset ‘count1’ and ‘count2’ to 0 to count the occurrences of the two candidates in the ‘nums’ array.

Count Check and Result:
- We check if the counts of ‘candidate1’ and ‘candidate2’ are greater than ⌊n/3⌋, where ‘n’ is the length of the ‘nums’ array.
- If the count of ‘candidate1’ is greater than ⌊n/3⌋, we add ‘candidate1’ to the result list.
- Similarly, if the count of ‘candidate2’ is greater than ⌊n/3⌋, we add ‘candidate2’ to the result list.

Codes :Boyer-Moore Majority Voting Appraoch

c++ : Boyer-Moore Majority Voting Appraoch


class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;

        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;

        // Count the occurrences of the candidates
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }

        vector<int> result;

        if (count1 > nums.size() / 3) {
            result.push_back(candidate1);
        }
        if (count2 > nums.size() / 3) {
            result.push_back(candidate2);
        }

        return result;
    }
};

Java:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;

        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;

        // Count the occurrences of the candidates
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }

        List<Integer> result = new ArrayList<>();

        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        if (count2 > nums.length / 3) {
            result.add(candidate2);
        }

        return result;
    }
}

Python:

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        candidate1, candidate2 = 0, 0
        count1, count2 = 0, 0

        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1
            elif count1 == 0:
                candidate1 = num
                count1 = 1
            elif count2 == 0:
                candidate2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        count1, count2 = 0, 0

        # Count the occurrences of the candidates
        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1

        result = []

        if count1 > len(nums) // 3:
            result.append(candidate1)
        if count2 > len(nums) // 3:
            result.append(candidate2)

        return result

JavaScript:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
         let candidate1 = 0, candidate2 = 0;
    let count1 = 0, count2 = 0;

    for (let num of nums) {
        if (num === candidate1) {
            count1++;
        } else if (num === candidate2) {
            count2++;
        } else if (count1 === 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 === 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    count1 = 0;
    count2 = 0;

    // Count the occurrences of the candidates
    for (let num of nums) {
        if (num === candidate1) {
            count1++;
        } else if (num === candidate2) {
            count2++;
        }
    }

    let result = [];

    if (count1 > nums.length / 3) {
        result.push(candidate1);
    }
    if (count2 > nums.length / 3) {
        result.push(candidate2);
    }

    return result;
};

Result Analysis Leet code 2038

List of Some important Leet code Questions: