Leet Code Solutions

Input: Array nums of integers sorted in non-decreasing order. Task: Remove some duplicates from nums in place such that each unique element appears at most twice. The relative order of elements should be kept the same. Output: Return k where k is the number of elements remaining after removing duplicates.

Idea: The main idea is to iterate once through the array keeping track of the current read index (just the iterator in the for loop) and the writeIndex. We need a bit of logic to deside when to write to nums[writeIndex] and when to update it.

We do this by keeping track of the number of duplicate elements seen in a row in currentDups. When a yet unseen element is encountered, reset this count to 1. So long as the number of duplicate elements in a row (currentDups) does not exceed the allowed number of duplicates (allowedDups) then write to the array.

Here are two slightly different solutions:

Solution 1

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int writeIndex = 1;
        int allowedDups = 2;   //the number of allowed appearances for a unique element
        int currentDups = 1;   //tracker for the number
        for (int i = 1; i < nums.size(); i++){
            if (nums[i - 1] != nums[i]){
                nums[writeIndex] = nums[i];
                currentDups = 1;
                writeIndex += 1;
            } else {
                currentDups += 1;
                if (currentDups <= allowedDups){
                    nums[writeIndex] = nums[i];
                    writeIndex += 1;
                }
            }
        }
        return writeIndex;
    }
};

Runtime: 0ms. Memory usage: 19.60 MB.

Solution 2

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int writeIndex = 1;
        int allowedDups = 2;
        int currentDups = 1;
        for (int i = 1; i < nums.size(); i++){
            if (nums[i - 1] != nums[i]){
                currentDups = 1;
            } else {
              currentDups += 1;
            }
            if (currentDups <= allowedDups){
                nums[writeIndex] = nums[i];
                writeIndex += 1;
            }
        }
        return writeIndex;
    }
};

Runtime: 5ms. Memory usage: 19.55 MB.

Difference between solutions

I prefer solution 2 since it avoids two duplicate lines, i.e. it only updates writeIndex and writes to nums[writeIndex] in one place. However, it is slightly slower due to branch optimization. The second solution has two separate if-else paths, but the first has only one. The second solution uses less memory likely because it compiles to slightly less machine code.

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Coming up with a solution is easy, here is one:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = {num : 0 for num in nums}

        for num in nums:
            count[num] += 1

        k = max(count, key=count.get)
        return k

It initializes a dictionary with one key-value pair for every unique element of nums, iterates through nums counting the occurances of each unique element and finally returns the maximum count. I’m not sure how long the max function nor the allocation of count takes, but it may still run in linear time technically. It’s still slow though, and it has suboptimal memory utilization.

Here’s the accepted optimal solution, known as the Boyer-Moore Majority Vote Algorithm. It works using a simple observation: if we pair up occurances of the majority element with a different element and cancel them, then the majority element will be the last one standing.

To implement this, we run a “vote” on the array. Votes are cast for or against a single current candidate. We iterate once through the array, keeping track of a candidate and a current count tally. Each element votes for itself if it is the candidate and against the current candidate if it is not the candidate.

At any point in the iteration:

• count is 0, then make the current element the candidate and set the count to 1.
• if the current element is the candidate, add 1 to count
• if the current element is not the candidate, remove 1 from the count.

Here is the implementation in python:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
                count = 1
            elif num == candidate:
                count += 1
            else:
                count -= 1
        return candidate

This only requires a single iteration through the array and only allocates additional memory for the integer count and the object candidate. Hence it runs in linear time and in O(1) space.