Majority Element - Leetcode 169 - TypeScript

Here's the Leetcode 169 solution using TypeScript.

Watch on Youtube

Leetcode 169 - Majority Element

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.

Approach

The goal is to find the majority element in an array, the majority is an element that appears more than ⌊n / 2⌋ times (where n is the length of the array).

There are several approaches to solve this problem, but the easiest approach is sorting the array and finding the element at the middle index.

After sorting, the majority element will always be at the middle index of the sorted array.

View on Excalidraw

Code Implementation

function majorityElement(nums: number[]): number {
  nums.sort((i, j) => i - j)
  const midIdx = Math.floor(nums.length / 2)
  return nums[midIdx]
}

Time Complexity

Time complexity is O(n log n), where n is the length of the input array nums. The dominating factor here is the sorting operation, which has a time complexity of O(n log n) for most sorting algorithms.

Space Complexity

Space complexity is O(1) or constant. The sorting is done in-place, it means the algorithm modifies the input array directly without using additional memory that grows with the size of the input array. The space required for variables like midIdx is constant regardless of the input size.