Summary of "Majority Element | Brute- Better-Best Approach | Moore's Voting Algorithm | & Pair Sum"

Summary of Video:

Majority Element | Brute- Better-Best Approach | Moore's Voting Algorithm | & Pair Sum

Main Topics Covered:

Pair Sum Problem (in a Sorted Array)
Majority Element Problem
- Brute Force Approach
- Sorting-Based Approach
- Moore’s Voting Algorithm (Optimized Approach)

1. Pair Sum Problem

Problem Statement: Given a sorted array and a target sum, find two numbers in the array whose sum equals the target. Return their indices.

Approaches:

Brute Force Approach:
- Use two nested loops to check all unique pairs.
- For each pair (i, j), check if nums[i] + nums[j] == target.
- If yes, return indices [i, j].
- Time Complexity: O(n²).
Optimized Two-Pointer Approach:
- Since the array is sorted, use two pointers: one at the start (i), one at the end (j).
- Calculate pair_sum = nums[i] + nums[j].
- If pair_sum == target, return [i, j].
- If pair_sum > target, decrement j to reduce sum.
- If pair_sum < target, increment i to increase sum.
- Stop when i < j.
- Time Complexity: O(n).

2. Majority Element Problem

Problem Statement: Given an array, find the Majority Element — the element that appears more than floor(n/2) times. It is guaranteed that such an element exists.

Brute Force Approach:

For each element, count its frequency by scanning the entire array.
If frequency > n/2, return that element.
Time Complexity: O(n²).

Sorting-Based Approach:

Sort the array (time complexity O(n log n)).
Since Majority Element appears more than half the time, it will be the middle element after sorting.
Traverse the sorted array to count frequencies of consecutive elements.
Return the element whose frequency exceeds n/2.
Time Complexity: O(n log n).

Moore’s Voting Algorithm (Optimized Approach):

Intuition: Majority Element’s frequency is so high that it "cancels out" all other elements.
Algorithm:
- Initialize count = 0 and candidate = None.
- Iterate through the array:
  - If count == 0, set candidate = current_element.
  - If current_element == candidate, increment count.
  - Else, decrement count.
- After the loop, candidate holds the Majority Element.
Time Complexity: O(n), Space Complexity: O(1).
If the Majority Element is not guaranteed, verify by counting frequency of candidate after the loop; if frequency > n/2, return candidate, else return -1.

Additional Notes:

The video also explains the logic behind Moore’s Voting Algorithm using the analogy of voting power and how the Majority Element always wins after cancellation.
For the Pair Sum Problem, the video emphasizes the importance of using given information (like the array being sorted) to optimize solutions.
The Majority Element problem is a classical DSA problem with multiple approaches from naive to optimal.
The video provides code snippets and dry runs for all discussed approaches.

Methodologies/Steps Outlined:

Pair Sum - Brute Force:

Nested loops with indices i and j (j > i).
Check sum of nums[i] + nums[j].
Return indices if sum equals target.

Pair Sum - Two Pointer:

Initialize i = 0, j = n-1.
While i < j:
- Compute sum.
- If sum == target, return [i, j].
- If sum > target, decrement j.
- Else increment i.

Majority Element - Brute Force:

For each element:
- Initialize frequency = 0.
- Loop through array counting occurrences.
- If frequency > n/2, return element.

Majority Element - Sorting:

Sort array.
Initialize frequency = 1, answer = first element.
Loop from second element to end:
- If current == previous, increment frequency.
- Else reset frequency to 1 and update answer.
- If frequency > n/2, return answer.

Majority Element - Moore’s Voting Algorithm:

Initialize count = 0, candidate = None.
For each element:
- If count == 0, candidate = element.
- If element == candidate, count++.
- Else count--.
Return candidate.
(Optional) Verify candidate frequency if Majority Element not guaranteed.