Majority Element Ii

                                            
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> result;
        int num1 = -1, num2 = -1, count1 = 0, count2 = 0;
        
        for (int num : nums) {
            if (num == num1) {
                count1++;
            } else if (num == num2) {
                count2++;
            } else if (count1 == 0) {
                num1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                num2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = count2 = 0;
        for (int num : nums) {
            if (num == num1) {
                count1++;
            } else if (num == num2) {
                count2++;
            }
        }
        
        if (count1 > nums.size() / 3) {
            result.push_back(num1);
        }
        if (count2 > nums.size() / 3) {
            result.push_back(num2);
        }
        
        return result;
    }
};

                                            
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        
        int num1 = 0, num2 = 0, count1 = 0, count2 = 0;
        
        for (int num : nums) {
            if (num == num1) {
                count1++;
            } else if (num == num2) {
                count2++;
            } else if (count1 == 0) {
                num1 = num;
                count1++;
            } else if (count2 == 0) {
                num2 = num;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int num : nums) {
            if (num == num1) {
                count1++;
            } else if (num == num2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(num1);
        }
        if (count2 > nums.length / 3) {
            result.add(num2);
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        count1, count2, candidate1, candidate2 = 0, 0, 0, 1
        
        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1
            elif count1 == 0:
                candidate1, count1 = num, 1
            elif count2 == 0:
                candidate2, count2 = num, 1
            else:
                count1 -= 1
                count2 -= 1
        
        return [n for n in (candidate1, candidate2) if nums.count(n) > len(nums) // 3]

                                            
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* majorityElement(int* nums, int numsSize, int* returnSize){
    int candidate1 = 0, candidate2 = 0;
    int count1 = 0, count2 = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate1) {
            count1++;
        } else if (nums[i] == candidate2) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = nums[i];
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = nums[i];
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    
    count1 = 0;
    count2 = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate1) {
            count1++;
        } else if (nums[i] == candidate2) {
            count2++;
        }
    }
    
    *returnSize = 0;
    if (count1 > numsSize / 3) (*returnSize)++;
    if (count2 > numsSize / 3 && candidate1 != candidate2) (*returnSize)++;
    
    int* res = (int*)malloc(sizeof(int) * (*returnSize));
    int index = 0;
    
    if (count1 > numsSize / 3) res[index++] = candidate1;
    if (count2 > numsSize / 3 && candidate1 != candidate2) res[index++] = candidate2;
    
    return res;
}

                                            
public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        List<int> result = new List<int>();
        if (nums == null || nums.Length == 0) {
            return result;
        }
        
        int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
        
        foreach (int num in 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;
        
        foreach (int num in nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.Length / 3) {
            result.Add(candidate1);
        }
        
        if (count2 > nums.Length / 3) {
            result.Add(candidate2);
        }
        
        return result;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    let count1 = 0, count2 = 0;
    let candidate1, candidate2;
    
    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;
    
    for (let num of nums) {
        if (num === candidate1) {
            count1++;
        } else if (num === candidate2) {
            count2++;
        }
    }
    
    const result = [];
    if (count1 > nums.length / 3) {
        result.push(candidate1);
    }
    if (count2 > nums.length / 3) {
        result.push(candidate2);
    }
    
    return result;
};

                                            
function majorityElement(nums: number[]): number[] {
    const threshold = Math.floor(nums.length / 3);
    const countMap: Map<number, number> = new Map();

    for (const num of nums) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }

    const result: number[] = [];
    for (const [num, count] of countMap) {
        if (count > threshold) {
            result.push(num);
        }
    }

    return result;
}

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function majorityElement($nums) {
        $count = [];

        foreach ($nums as $num) {
            if (isset($count[$num])) {
                $count[$num]++;
            } else {
                $count[$num] = 1;
            }
        }

        $result = [];
        $threshold = floor(count($nums) / 3);

        foreach ($count as $num => $freq) {
            if ($freq > $threshold) {
                $result[] = $num;
            }
        }

        return $result;
    }
}

                                            
class Solution {
    func majorityElement(_ nums: [Int]) -> [Int] {
        var num1: Int?
        var num2: Int?
        var count1 = 0
        var count2 = 0
        
        for num in nums {
            if let num1 = num1, num == num1 {
                count1 += 1
            } else if let num2 = num2, num == num2 {
                count2 += 1
            } else if count1 == 0 {
                num1 = num
                count1 = 1
            } else if count2 == 0 {
                num2 = num
                count2 = 1
            } else {
                count1 -= 1
                count2 -= 1
            }
        }
        
        count1 = 0
        count2 = 0
        for num in nums {
            if num == num1 {
                count1 += 1
            } else if num == num2 {
                count2 += 1
            }
        }
        
        var result: [Int] = []
        if count1 > nums.count/3 {
            result.append(num1!)
        }
        if count2 > nums.count/3 {
            result.append(num2!)
        }
        
        return result
    }
}

                                            
class Solution {
    fun majorityElement(nums: IntArray): List<Int> {
        val result = mutableListOf<Int>()
        var candidate1: Int? = null
        var count1 = 0
        var candidate2: Int? = null
        var count2 = 0
        
        for (num in nums) {
            when {
                candidate1 == num -> count1++
                candidate2 == num -> count2++
                count1 == 0 -> {
                    candidate1 = num
                    count1 = 1
                }
                count2 == 0 -> {
                    candidate2 = num
                    count2 = 1
                }
                else -> {
                    count1--
                    count2--
                }
            }
        }
        
        count1 = 0
        count2 = 0
        
        for (num in nums) {
            if (num == candidate1) count1++
            else if (num == candidate2) count2++
        }
        
        if (count1 > nums.size / 3) result.add(candidate1!!)
        if (count2 > nums.size / 3) result.add(candidate2!!)
        
        return result
    }
}

                                            
class Solution {
  List<int> majorityElement(List<int> nums) {
    List<int> result = [];
    if (nums.isEmpty) {
      return result;
    }
    int num1 = nums[0];
    int count1 = 0;
    int num2 = nums[0];
    int count2 = 0;

    for (int num in nums) {
      if (num == num1) {
        count1++;
      } else if (num == num2) {
        count2++;
      } else if (count1 == 0) {
        num1 = num;
        count1 = 1;
      } else if (count2 == 0) {
        num2 = num;
        count2 = 1;
      } else {
        count1--;
        count2--;
      }
    }

    count1 = count2 = 0;
    for (int num in nums) {
      if (num == num1) {
        count1++;
      } else if (num == num2) {
        count2++;
      }
    }

    if (count1 > nums.length ~/ 3) {
      result.add(num1);
    }
    if (count2 > nums.length ~/ 3) {
      result.add(num2);
    }

    return result;
  }
}

                                            
func majorityElement(nums []int) []int {
    var num1, num2, count1, count2 int

    for _, num := range nums {
        if num == num1 {
            count1++
        } else if num == num2 {
            count2++
        } else if count1 == 0 {
            num1 = num
            count1++
        } else if count2 == 0 {
            num2 = num
            count2++
        } else {
            count1--
            count2--
        }
    }

    count1 = 0
    count2 = 0
    for _, num := range nums {
        if num == num1 {
            count1++
        } else if num == num2 {
            count2++
        }
    }

    result := make([]int, 0)
    if count1 > len(nums)/3 {
        result = append(result, num1)
    }
    if count2 > len(nums)/3 {
        result = append(result, num2)
    }

    return result
}

                                            
# @param {Integer[]} nums
# @return {Integer[]}
def majority_element(nums)
    count1, count2, candidate1, candidate2 = 0, 0, 0, 1
    
    nums.each do |num|
        if num == candidate1
            count1 += 1
        elsif num == candidate2
            count2 += 1
        elsif count1 == 0
            candidate1 = num
            count1 = 1
        elsif count2 == 0
            candidate2 = num
            count2 = 1
        else
            count1 -= 1
            count2 -= 1
        end
    end
    
    count1, count2 = 0, 0
    nums.each do |num|
        count1 += 1 if num == candidate1
        count2 += 1 if num == candidate2
    end
    
    result = []
    result << candidate1 if count1 > nums.length / 3
    result << candidate2 if count2 > nums.length / 3
    
    result
end

                                            
object Solution {
    def majorityElement(nums: Array[Int]): List[Int]  = {
        var count1 = 0
        var count2 = 0
        var candidate1 = 0
        var candidate2 = 1

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

        count1 = 0
        count2 = 0

        for (num <- nums) {
            if (num == candidate1) {
                count1 += 1
            } else if (num == candidate2) {
                count2 += 1
            }
        }

        val result = scala.collection.mutable.ListBuffer[Int]()
        if (count1 > nums.length / 3) {
            result += candidate1
        }
        if (count2 > nums.length / 3) {
            result += candidate2
        }

        result.toList
    }
}

                                            
impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> Vec<i32> {
        let mut count1 = 0;
        let mut count2 = 0;
        let mut candidate1 = 0;
        let mut candidate2 = 1;
        
        for &num in nums.iter() {
            if candidate1 == num {
                count1 += 1;
            } else if candidate2 == num {
                count2 += 1;
            } else if count1 == 0 {
                candidate1 = num;
                count1 = 1;
            } else if count2 == 0 {
                candidate2 = num;
                count2 = 1;
            } else {
                count1 -= 1;
                count2 -= 1;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for &num in nums.iter() {
            if num == candidate1 {
                count1 += 1;
            } else if num == candidate2 {
                count2 += 1;
            }
        }
        
        let mut result = Vec::new();
        if count1 > nums.len() / 3 {
            result.push(candidate1);
        }
        if count2 > nums.len() / 3 {
            result.push(candidate2);
        }
        
        result
    }
}

                                            
(define/contract (majority-element nums)
  (-> (listof exact-integer?) (listof exact-integer?))
  (define count (make-hash))
  (define threshold (quotient (length nums) 3))
  (for ([num nums])
    (hash-update! count num add1 0))
  (for/list ([key (in-hash-keys count)]
             #:when (> (hash-ref count key) threshold))
    key) )

                                            
defmodule Solution do
  @spec majority_element(nums :: [integer]) :: [integer]
  def majority_element(nums) do
    n = length(nums)
    threshold = div(n, 3)
    
    nums
    |> Enum.reduce(%{}, fn num, acc ->
      Map.update(acc, num, 1, &(&1 + 1))
    end)
    |> Enum.filter(fn {_num, count} -> count > threshold end)
    |> Enum.map(fn {num, _count} -> num end)
  end
end

To solve this coding challenge, we need to identify all elements in an integer array that appear more than ⌊n/3⌋ times. The problem demands an O(n) time complexity and O(1) space complexity, making the solution non-trivial. We're utilizing a modified version of the Boyer-Moore Voting Algorithm to achieve this.

Explanation

Here, we try to find elements in the array which appear more than

n/3

times. This involves a few key steps:

Candidate Selection: We first try to identify up to two potential candidates that might be the majority elements. This is because there can be at most 2 elements in an array that appear more than ⌊n/3⌋ times. We use a counter approach for this.
Validation Phase: After identifying the candidates, we need to verify them by counting their actual occurrences in the array.

Step-by-Step Explanation

Initialization :

Create two candidate variables and their associated counts, initializing counts to 0.

First Pass (Candidate Identification) :

Iterate through the array.
Adjust counts based on the current element and update candidates if necessary.

Second Pass (Validation) :

Count the occurrences of the identified candidates.
Check if they meet the required
n/3

threshold.

Detailed Steps in Pseudocode:

Initialization Phase:

Initialize variables
candidate1

,
candidate2

to hold potential candidates. Set initial values.
Initialize
count1

and
count2

to 0, which will track the count of appearances for
candidate1

and
candidate2

, respectively.

                                            
# Initialize counters and candidates
count1 = 0
count2 = 0
candidate1 = None
candidate2 = None

First Pass: Candidate Identification

Iterate through each number
num

in the array
nums

:

If
num

equals
candidate1

, increment
count1

.
Else if
num

equals
candidate2

, increment
count2

.
Else if
count1

is 0, set
candidate1

to
num

and
count1

to 1.
Else if
count2

is 0, set
candidate2

to
num

and
count2

to 1.
Otherwise, decrement both
count1

and
count2

.

                                            
# Iterate through the array to identify potential candidates
for num in nums:
if num == candidate1:
count1 += 1  # Increment count for candidate1
elif num == candidate2:
count2 += 1  # Increment count for candidate2
elif count1 == 0:
candidate1 = num  # Set new candidate1
count1 = 1        # Initialize count1
elif count2 == 0:
candidate2 = num  # Set new candidate2
count2 = 1        # Initialize count2
else:
count1 -= 1  # Decrement count1
count2 -= 1  # Decrement count2

Second Pass: Validation Phase

Reset counts to 0 for the second pass:

count1

for validating
candidate1

.
count2

for validating
candidate2

.

Iterate through the array again to count the actual occurrences of
candidate1

and
candidate2

.
Check if
candidate1

or
candidate2

occur more than
n/3

times. If they do, add them to the result list.

                                            
# Reset counts for validation
count1 = 0
count2 = 0

# Count occurrences of candidate1 and candidate2 in the array
for num in nums:
    if num == candidate1:
        count1 += 1  # Increment count for candidate1
    elif num == candidate2:
        count2 += 1  # Increment count for candidate2

# Prepare the result list
result = []

# Verify if candidates appear more than n/3 times
if count1 > len(nums) / 3:
    result.append(candidate1)  # Add candidate1 to result
if count2 > len(nums) / 3:
    result.append(candidate2)  # Add candidate2 to result

# Result contains the majority elements
return result

This approach ensures a time complexity of O(n) and space complexity of O(1). The detailed steps break down how we first select potential candidates and then validate them, ensuring thorough understanding of each phase in this algorithm.