This section covers medium-difficulty array problems commonly encountered in technical interviews and real-world software engineering. Each problem includes a detailed explanation of the core concept, step-by-step example walkthroughs, Python source code, and time/space complexity analysis.

1. Majority Element (Boyer-Moore Voting Algorithm)¶

Problem Description¶

Given an array nums of size \(N\), find the majority element. The majority element is defined as the element that appears strictly more than \(\lfloor N / 2 \rfloor\) times in the array.

If no majority element exists, return -1.

Intuition & Approach¶

1. Naive / Hash Map Approach¶

A straightforward way to solve this is using a hash map (or dictionary) to count the frequency of each element: - Traverse the array and store element frequencies in a hash map. - Iterate through the hash map to find an element with frequency \(\ge \lfloor N / 2 \rfloor\). - Complexity: Time \(\mathcal{O}(N)\), Space \(\mathcal{O}(N)\).

2. Boyer-Moore Voting Algorithm (\(\mathcal{O}(1)\) Extra Space)¶

The Boyer-Moore Voting Algorithm allows us to find the majority candidate in linear time \(\mathcal{O}(N)\) using only \(\mathcal{O}(1)\) auxiliary space.

Key Insight: If we pair up different elements in the array and cancel them out, the majority element (which appears more than half the time) will always remain at the end.

Algorithm Steps: 1. Candidate Finding Phase: - Maintain a candidate variable and a count counter initialized to 0. - Iterate through nums: - If count == 0, assign candidate = current_element and reset count = 1. - Else if current_element == candidate, increment count += 1. - Else, decrement count -= 1. 2. Verification Phase: - Because a majority element is not guaranteed in every input array, verify the candidate by counting its actual occurrences in nums. - If count >= len(nums) // 2, return candidate. Otherwise, return -1.

Example Walkthrough¶

Input: nums = [7, 0, 0, 1, 7, 7, 2, 7, 7]
(\(N = 9\), threshold \(\lfloor 9/2 \rfloor = 4\))

Phase 1: Candidate Selection¶

Result Candidate: 7

Phase 2: Candidate Verification¶

• Count occurrences of 7 in nums: 5 times.
• Check condition: 5 >= 9 // 2 (\(5 \ge 4\)) is True.
• Output: 7

Python Solution¶

class Solution:
    def majority_elements(self, nums: list) -> int:
        candidate = -1
        count = 0

        for index, el in enumerate(nums):
            if count == 0:
                candidate = el
                count = 1
            elif candidate == el:
                count += 1
            else:
                count -= 1

        count = 0
        for el in nums:
            if el == candidate: count += 1

        if count >= len(nums) // 2:
            return candidate

        return -1

#   main function for the program
def main():
    sol = Solution()
    nums = [7, 0, 0, 1, 7, 7, 2, 7, 7]

    print(sol.majority_elements(nums))

#   driver code for the program
if __name__ == '__main__':
    main()

Complexity Analysis¶

• Time Complexity: \(\mathcal{O}(N)\)
• Phase 1 takes \(\mathcal{O}(N)\) time for candidate selection.
• Phase 2 takes \(\mathcal{O}(N)\) time for verification.

• Total time complexity is \(2 \times \mathcal{O}(N) = \mathcal{O}(N)\).

• Space Complexity: \(\mathcal{O}(1)\)

• Operates in-place using constant auxiliary variables (candidate and count).

2. Leaders in an Array¶

Problem Description¶

Given an array nums, find all the leader elements in the array. An element is considered a leader if it is strictly greater than all elements present to its right.

Note: The rightmost element is always considered a leader because there are no elements to its right.

Intuition & Approach¶

1. Naive Nested Loop (\(\mathcal{O}(N^2)\))¶

For each element at index i, loop through all elements from i + 1 to N - 1 to check if nums[i] is greater than every element to its right.

2. Optimal Right-to-Left Scan (\(\mathcal{O}(N)\))¶

Instead of scanning left-to-right, scan the array from right to left: 1. Keep track of the maximum element seen so far from the right end, stored in right_most. 2. The last element nums[-1] is always a leader. Initialize right_most = nums[-1] and append nums[-1] to ans. 3. Loop backwards from len(nums) - 2 down to 0: - If nums[index] > right_most: We found a new leader! Update right_most = nums[index] and append it to ans. 4. Reverse ans (ans[::-1]) to return the leaders in their original left-to-right order.

Example Walkthrough¶

Input: nums = [1, 2, 5, 3, 1, 2]

Reversing ans \(\rightarrow\) [5, 3, 2]

Output: [5, 3, 2]

Python Solution¶

class Solution:
    def leaders(self, nums: list) -> list:
        ans = []
        if len(nums) == 0: return ans

        ans.append(nums[-1])
        right_most = nums[-1]

        index = len(nums) - 2
        while index >= 0:
            if nums[index] > right_most:
                right_most = nums[index]
                ans.append(right_most)
            index -= 1

        return ans[::-1]

#   main function for the program
def main():
    sol = Solution()
    nums = [1, 2, 5, 3, 1, 2]

    print(sol.leaders(nums))

#   driver code for the program
if __name__ == '__main__':
    main()

Complexity Analysis¶

• Time Complexity: \(\mathcal{O}(N)\)
• Backward scan visits each of the \(N\) elements once.
• Reversing the resulting ans list takes \(\mathcal{O}(K)\) time (where \(K \le N\)).

• Total time complexity is \(\mathcal{O}(N)\).

• Space Complexity: \(\mathcal{O}(1)\) auxiliary space (excluding the output array ans).

3. Rearrange Array Elements by Sign¶

Problem Description¶

Given a 0-indexed integer array nums of even length containing an equal number of positive and negative integers, rearrange the elements of nums such that:

1. Every consecutive pair of integers has alternating signs.
2. For all integers with the same sign, the relative order in which they appeared in nums is preserved.
3. The rearranged array begins with a positive integer (positive elements at even indices 0, 2, 4..., negative elements at odd indices 1, 3, 5...).

Intuition & Two-Pointer Placement Approach¶

Since positive integers must end up at even indices (0, 2, 4...) and negative integers at odd indices (1, 3, 5...), we can populate a new result array ans of length \(N\) in a single pass:

1. Initialize pos_index = 0 (points to the next available even index).
2. Initialize neg_index = 1 (points to the next available odd index).
3. Iterate through nums:
4. If el > 0: Assign ans[pos_index] = el and advance pos_index += 2.
5. If el < 0: Assign ans[neg_index] = el and advance neg_index += 2.
6. Return ans.

Example Walkthrough¶

Input: nums = [2, 4, 5, -1, -3, -4]

Output: [2, -1, 4, -3, 5, -4]

Python Solution¶

class Solution:
    def rearrange_array(self, nums: list) -> list:
        ans = [0] * len(nums)
        pos_index, neg_index = 0, 1

        for index, el in enumerate(nums):
            if el < 0:
                ans[neg_index] = el
                neg_index += 2
            else:
                ans[pos_index] = el
                pos_index += 2

        return ans

#   main function for the program
def main():
    sol = Solution()
    nums = [2, 4, 5, -1, -3, -4]

    print(sol.rearrange_array(nums))

#   driver code for the program
if __name__ == '__main__':
    main()

Complexity Analysis¶

• Time Complexity: \(\mathcal{O}(N)\) — Linear scan traversing the \(N\) elements once.
• Space Complexity: \(\mathcal{O}(N)\) — Memory allocated for the output array ans of size \(N\).

4. Sum and Target Based Problems (Two Sum & Three Sum)¶

Problem Description¶

1. Two Sum: Given an array nums and a target, return the 0-based indices of the two numbers that sum to target.
2. Two Sum Exists: Given an array nums and a target, return True if any pair sums to target, else False.
3. Three Sum: Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that \(i \neq j \neq k\) and \(\text{nums}[i] + \text{nums}[j] + \text{nums}[k] = 0\).

Intuition & Approach¶

Two Sum (Hash Map Approach)¶

Instead of a nested loop (\(\mathcal{O}(N^2)\)), use a hash map to record visited elements and their indices: - For each element el at index, calculate complement required = target - el. - If required exists in hash_map, return [hash_map[required], index]. - Otherwise, store hash_map[el] = index.

Three Sum (Sorting + Two Pointers)¶

1. Sort nums in non-decreasing order (\(\mathcal{O}(N \log N)\)).
2. Iterate i from 0 to len(nums) - 3:
3. Skip duplicate values for nums[i] to avoid duplicate triplets.
4. Set two pointers: left = i + 1, right = len(nums) - 1.
5. While left < right:
   • Calculate s = nums[i] + nums[left] + nums[right].
   • If s == 0: Found a triplet! Append [nums[i], nums[left], nums[right]], then increment left and decrement right while skipping duplicate values.
   • Else if s < 0: Increment left += 1 to increase the sum.
   • Else (s > 0): Decrement right -= 1 to decrease the sum.

Example Walkthrough (Two Sum)¶

Input: nums = [1, 6, 2, 10, 3], target = 7

Output: [0, 1]

Python Solution¶

class Solution:
    def two_sum(self, nums: list, target: int) -> list:
        ans = [-1, -1]
        hash_map = {}

        for index, el in enumerate(nums):
            if (target - el) in hash_map:
                return [hash_map[target - el], index]

            hash_map[el] = index

        return ans

    def two_sum_exists(self, nums: list, target: int) -> bool:
        s = set()
        for el in nums:
            if target - el in s:
                return True
            s.add(el)

        return False

    def three_sum(self, nums: list) -> list:
        nums.sort()
        ans = []
        n = len(nums)

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if s == 0:
                    ans.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1

                    while right > left and nums[right] == nums[right + 1]:
                        right -= 1
                elif s < 0:
                    left += 1
                else:
                    right -= 1

        return ans

#   main function for the program
def main():
    sol = Solution()
    nums = [1, 6, 2, 10, 3]
    target = 7

    print(sol.two_sum(nums, target))

#   driver code for the program
if __name__ == '__main__':
    main()

Complexity Analysis¶

• Two Sum:
• Time Complexity: \(\mathcal{O}(N)\) — Single pass using \(\mathcal{O}(1)\) average hash map lookup.

• Space Complexity: \(\mathcal{O}(N)\) — Space stored in hash_map.

• Three Sum:

• Time Complexity: \(\mathcal{O}(N^2)\) — Sorting takes \(\mathcal{O}(N \log N)\) and the nested two-pointer scan takes \(\mathcal{O}(N^2)\).
• Space Complexity: \(\mathcal{O}(1)\) auxiliary space (excluding output list).

5. Pascal's Triangle Problems¶

Problem Description¶

Pascal's Triangle is a triangular array of numbers where each entry is the sum of the two numbers directly above it.

1. Variation 1 (pascal_triangle_one): Given 1-indexed row r and column c, return the value at element \((r, c)\).
2. Variation 2 (pascal_triangle_two): Given 1-indexed row r, return all values in the \(r\)-th row.
3. Variation 3 (pascal_triangle_three): Given integer n, return the first n rows of Pascal's Triangle.

Intuition & Mathematical Formula¶

Any element at row \(r\) and column \(c\) (1-indexed) in Pascal's Triangle corresponds to the mathematical combination: $\(\text{Element}(r, c) = \binom{r - 1}{c - 1} = \frac{(r - 1)!}{(c - 1)! \times (r - c)!}\)$

Approach¶

• Compute factorials \(\text{fact}(n) = n!\).
• Compute combination \(\binom{r}{c} = \frac{r!}{c! \times (r - c)!}\).
• Use combination helper to calculate individual positions or build row vectors.

Example Walkthrough¶

Pascal's Triangle Structure:

Row 1:        1
Row 2:      1   1
Row 3:    1   2   1
Row 4:  1   3   3   1

• pascal_triangle_one(4, 2) \(\rightarrow \binom{4-1}{2-1} = \binom{3}{1} = 3\)
• pascal_triangle_two(4) \(\rightarrow \left[\binom{3}{0}, \binom{3}{1}, \binom{3}{2}, \binom{3}{3}\right] = [1, 3, 3, 1]\)
• pascal_triangle_three(4) \(\rightarrow [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]\)

Python Solution¶

class Solution:
    def __factorial__(self, num: int) -> int:
        fact = 1
        for i in range(1, num + 1):
            fact = fact * i

        return fact

    def __combination__(self, r: int, c: int) -> int:
        return (
            self.__factorial__(r) // (self.__factorial__(c) * self.__factorial__(r - c))
        )

    """
    Given two integers r and c.
    Return the value at the rth row and cth column (1-indexed) in a Pascal's Triangle.
    """
    def pascal_triangle_one(self, r: int, c: int) -> int:
        return self.__combination__(r - 1, c - 1)

    """
    Given an integer r, return all the values in the rth row (1-indexed) in Pascal's Triangle in correct order.
    """
    def pascal_triangle_two(self, r: int) -> list:
        ans = []
        for i in range(r):
            ans.append(self.__combination__(r - 1, i))

        return ans

    """
    Given an integer n, return the first n (1-Indexed) rows of Pascal's triangle.
    """
    def pascal_triangle_three(self, n: int) -> list:
        ans = []
        if n == 0: return []
        if n == 1: return [1]
        if n == 2: return [[1], [1,1]]

        for i in range(1, n + 1):
            out = []
            for j in range(i):
                out.append(self.__combination__(i - 1, j))
            ans.append(out)

        return ans

#   main function for the program
def main():
    sol = Solution()
    r = 4
    c = 2

    print(sol.pascal_triangle_one(r, c))
    print(sol.pascal_triangle_two(4))
    print(sol.pascal_triangle_three(4))

#   driver code for the program
if __name__ == '__main__':
    main()

Complexity Analysis¶

• Time Complexity:
• pascal_triangle_one: \(\mathcal{O}(r)\) to compute factorials.
• pascal_triangle_two: \(\mathcal{O}(r^2)\) computing combinations for row \(r\).

• pascal_triangle_three: \(\mathcal{O}(n^3)\) computing combinations for each entry up to row \(n\).

• Space Complexity: \(\mathcal{O}(1)\) auxiliary space (excluding result lists).

6. Sort Zeroes, Ones, and Twos (Dutch National Flag Algorithm)¶

Problem Description¶

Given an array nums containing only 0s, 1s, and 2s, sort the array in-place so that all 0s come first, followed by all 1s, and then all 2s.

You must solve this problem in-place without using built-in sort functions.

Intuition & Dutch National Flag Algorithm¶

The Dutch National Flag Algorithm (formulated by Edsger Dijkstra) uses 3 pointers (left, mid, right) to partition the array into 4 zones in a single pass:

[0 ... left-1]  --> All 0s
[left ... mid-1] --> All 1s
[mid ... right]  --> Unprocessed / Unknown elements
[right+1 ... N-1]--> All 2s

Algorithm Steps:¶

1. Initialize left = 0, mid = 0, right = len(nums) - 1.
2. Loop while mid <= right:
3. If nums[mid] == 0: Swap nums[left] and nums[mid]. Increment left += 1 and mid += 1.
4. If nums[mid] == 1: Element is already in correct middle zone. Increment mid += 1.
5. If nums[mid] == 2: Swap nums[mid] and nums[right]. Decrement right -= 1 (do not increment mid yet, as the swapped element from right needs inspection).

Example Walkthrough¶

Input: nums = [1, 0, 2, 1, 0]

mid = 4 > right = 3 \(\rightarrow\) Loop terminates.

Output: [0, 0, 1, 1, 2]

Python Solution¶

class Solution:
    def sort_zero_one_two(self, nums: list) -> None:
        left, right = 0, len(nums) - 1
        mid = 0

        while mid <= right:
            if nums[mid] == 0:
                nums[left], nums[mid] = nums[mid], nums[left]
                left += 1
                mid += 1
            elif nums[mid] == 2:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1
            else:
                mid += 1

#   main function for the program
def main():
    sol = Solution()
    nums = [1, 0, 2, 1, 0]

    sol.sort_zero_one_two(nums)
    print(nums)

#   driver code for the program
if __name__ == '__main__':
    main()

7. Maximum Subarray Sum (Kadane's Algorithm)¶

Problem Description¶

Given an integer array nums, find the contiguous subarray (containing at least one element) which has the largest sum and return its maximum sum.

Intuition & Kadane's Algorithm¶

1. Naive / Brute Force Approach (\(\mathcal{O}(N^2)\))¶

Check all possible contiguous subarrays nums[i...j] using nested loops, compute their sums, and record the maximum.

2. Kadane's Algorithm (\(\mathcal{O}(N)\) Single Pass)¶

Kadane's Algorithm dynamic programming approach optimizes this to linear time:

• Key Insight: If a running sum of a contiguous subarray becomes negative, carrying it forward into future elements will only reduce their total sum. Therefore, whenever the cumulative sum cont_sum drops below 0, we reset cont_sum = 0 to start a fresh candidate subarray from the next element.

Algorithm Steps: 1. Initialize max_sum = -float("inf") (to handle all-negative arrays correctly) and cont_sum = 0. 2. Iterate through each element el in nums: - Add el to cont_sum: cont_sum += el. - Update max_sum: max_sum = max(max_sum, cont_sum). - If cont_sum < 0: Reset cont_sum = 0 (discard negative prefix). 3. Return max_sum.

Example Walkthrough¶

Input: nums = [-2, -3, -7, -2, -10, -4]
(All-negative array case)

Output: -2

Python Solution¶

class Solution:
    def max_sub_array(self, nums: list) -> int:
        max_sum = -float("inf")
        cont_sum = 0

        for index, el in enumerate(nums):
            cont_sum += el
            max_sum = max(max_sum, cont_sum)

            if cont_sum < 0:
                cont_sum = 0

        return max_sum

#   main function for the program
def main():
    sol = Solution()
    nums = [-2, -3, -7, -2, -10, -4]

    print(sol.max_sub_array(nums))

#   driver code for the program
if __name__ == '__main__':
    main()

Complexity Analysis¶

• Time Complexity: \(\mathcal{O}(N)\) — Single pass linear scan traversing the \(N\) elements once.
• Space Complexity: \(\mathcal{O}(1)\) — Constant auxiliary space using scalar variables (max_sum and cont_sum).