Day-3 Leetcode Interview Questions

169. Majority Element — LeetCode (Easy)

Problem Summary

You are given an integer array nums of size n.

Your task is to return the majority element, which is defined as:

• The element that appears more than ⌊ n / 2 ⌋ times

• It is guaranteed that a majority element always exists in the input

Key Points:

• Majority element appears more than half the size of the array.

• It is guaranteed to exist → no need for checks.

• Must find it in O(n) time and O(1) space ideally.

Intuition / Approach

The optimal solution uses the famous Boyer–Moore Voting Algorithm.

Why this works:

• If we pair each occurrence of the majority element with a different element, the majority element will always remain because it appears more than half of the time.

• We keep:

  • candidate → current majority candidate

  • count → how strongly this candidate is supported

How it works:

1. Start with count = 0.

2. Traverse each element in the array:

   • If count == 0, choose the current number as the new candidate.

   • If the current number equals the candidate, increment count.

   • Otherwise, decrement count.

Since the majority element occurs more than all others combined, it will remain as the final candidate.

No sorting needed
No extra space required
Linear time (O(n))

Java Solution

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
            }
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}

Time & Space Complexity

189. Rotate Array — LeetCode (Medium)

Problem Summary

You are given an integer array nums and a non-negative integer k.

Your task is to rotate the array to the right by k steps.

A right rotation means elements shift to the right, and elements at the end wrap around to the front.

Example Walkthrough

Example 1:

• Input: nums = [1,2,3,4,5,6,7], k = 3

• Output: [5,6,7,1,2,3,4]

Explanation:

• After 1 rotation → [7,1,2,3,4,5,6]

• After 2 rotations → [6,7,1,2,3,4,5]

• After 3 rotations → [5,6,7,1,2,3,4]

Example 2:

• Input: nums = [-1,-100,3,99], k = 2

• Output: [3,99,-1,-100]

Intuition / Approach

A straightforward rotation would require shifting elements one by one, but that would be inefficient (O(n × k)) for large arrays.

We aim for an O(n) time and O(1) space solution.

The optimal trick is to use the reverse approach:

Key Insight:

To rotate the array right by k:

1. Reverse the entire array.

2. Reverse the first k elements.

3. Reverse the remaining part from k to n-1.

Why this works:

• Reversing the full array brings the last k elements to the front.

• Reversing the first k restores them to their correct order.

• Reversing the rest fixes the remaining elements.

Why do we use k = k % n?

If k is larger than the array length n, rotating more than n times is unnecessary because every n rotations brings the array back to its original form.

Example:
If nums = [1,2,3,4,5] and k = 12

Since 12 % 5 = 2, rotating 12 times is the same as rotating just 2 times.

So:

• k = k % n ensures we only rotate the essential number of times.

• It prevents index overflow and avoids extra unnecessary work.

Java Solution

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start <= end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Time & Space Complexity