Data Structures & Algorithms Arrays

Arrays: Hard Level Questions & Solutions

8 min read Engineering notes

This section covers hard array problems commonly encountered in technical interviews. Each problem includes the problem statement, the core idea behind the solution, an example, and complexity analysis.

1. Majority Elements II

Problem Description

Given an integer array nums of size N, return all elements that appear more than N / 3 times.

The answer can contain at most two elements. Return the elements in any order.

Intuition & Approach

1. Hash Map Approach

A hash map can count every element in O(N) time and space. After counting, return the elements whose frequency is greater than N / 3.

2. Extended Boyer-Moore Voting Algorithm

There can be at most two elements that appear more than N / 3 times. We therefore track two candidates and their counts:

When a candidate count reaches zero, use the current element as a candidate if it is not already the other candidate.
Increase the matching candidate's count.
When the current element matches neither candidate, decrement both counts. This cancels one occurrence of each candidate against two different elements.
Make a second pass to verify the actual frequency of both candidates, because the voting phase only produces possible candidates.

Example Walkthrough

Input: nums = [1, 1, 1, 3, 3, 2, 2, 2]
(N = 8, threshold N / 3 = 2)

The voting phase identifies 1 and 2 as the two possible candidates. The verification phase counts three occurrences of each, so both satisfy the condition.

Output: [1, 2]

Python Solution

class Solution:
    def majorityElementTwo(self, nums):
        ans = []
        candidate1, count1 = 0, 0
        candidate2, count2 = 0, 0

        for el in nums:
            if count1 == 0 and el != candidate2:
                count1 = 1
                candidate1 = el
            elif count2 == 0 and el != candidate1:
                candidate2 = el
                count2 = 1
            elif el == candidate1:
                count1 += 1
            elif el == candidate2:
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1

        count1, count2 = 0, 0

        for el in nums:
            if el == candidate1: count1 += 1
            elif el == candidate2: count2 += 1

        if count1 > len(nums) // 3: ans.append(candidate1)
        if count2 > len(nums) // 3: ans.append(candidate2)

        return ans

Complexity Analysis

Time Complexity: O(N) for the voting pass and verification pass.
Space Complexity: O(1) auxiliary space, excluding the output list.

2. Find the Repeating and Missing Numbers

Problem Description

Given an array nums of length N containing numbers from 1 to N, exactly one number appears twice and exactly one number is missing. Find the repeating number and the missing number.

Return the result as [repeating, missing].

Intuition & Approach

Let sum_actual and sum_expected be the sum of the array and the sum of numbers from 1 to N. Their difference gives:

repeating - missing = sum_actual - sum_expected

Do the same with squares. Dividing the difference of squared sums by the difference of sums gives:

repeating + missing = (repeating^2 - missing^2) / (repeating - missing)

With the sum and difference of the two unknown values, solve for both values. The final scan determines which one is repeating and which one is missing.

Example Walkthrough

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

The numbers from 1 to 5 should sum to 15, but the array sums to 14, so repeating - missing = -1. Comparing squared sums provides the second equation, which identifies 3 as the repeating value and 4 as the missing value.

Output: [3, 4]

Python Solution

class Solution:
    def findMissingRepeatingNumbers(self, nums):
        s1, s2 = 0, 0
        n = len(nums)

        for el in nums:
            s1 += el

        s2 = n * (n + 1) // 2

        difference = s1 - s2

        s1, s2 = 0, 0
        for el in nums:
            s1 += (el * el)

        s2 = n * (n + 1) * (2 * n + 1) // 6

        squared_difference = (s1 - s2) // difference

        first = (difference + squared_difference) // 2
        second = squared_difference - first

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

        if count > 1:
            repeating = first
            missing = second
        else:
            repeating = second
            missing = first

        return [repeating, missing]

Complexity Analysis

Time Complexity: O(N) across the sum, squared-sum, and verification passes.
Space Complexity: O(1) auxiliary space.

3. Count Inversions

Problem Description

Given an array nums, count the number of inversions. An inversion is a pair of indices (i, j) such that i < j and nums[i] > nums[j].

Intuition & Approach

1. Brute-Force Approach

Check every pair of indices and count the pairs satisfying the inversion condition. This takes O(N²) time.

2. Merge Sort Approach

Merge sort keeps the left and right halves sorted. During a merge:

If the current left value is less than or equal to the current right value, copy the left value.
Otherwise, the current right value is smaller than every remaining value in the left half. Add the number of remaining left values, mid - i + 1, to the inversion count.
Merge the remaining values and continue recursively.

Example Walkthrough

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

The inversion pairs include (5, 3), (5, 2), (5, 4), (5, 1), (3, 2), (3, 1), (2, 1), and (4, 1).

Output: 8

Python Solution

class Solution:
    def merge(self, nums: list, low: int, mid: int, high: int) -> int:
        count = 0
        i, j = low, mid + 1
        sorted_array = []

        while i <= mid and j <= high:
            if nums[i] <= nums[j]:
                sorted_array.append(nums[i])
                i += 1
            else:
                count += (mid - i + 1)
                sorted_array.append(nums[j])
                j += 1

        while i <= mid:
            sorted_array.append(nums[i])
            i += 1

        while j <= high:
            sorted_array.append(nums[j])
            j += 1

        for el in sorted_array:
            nums[low] = el
            low += 1

        return count

    def merge_sort(self, nums: list, low: int, high: int) -> int:
        count = 0
        if low < high:
            mid = (low + high) // 2
            count += self.merge_sort(nums, low, mid)
            count += self.merge_sort(nums, mid + 1, high)
            count += self.merge(nums, low, mid, high)

        return count

    def numberOfInversions(self, nums):
        return self.merge_sort(nums, 0, len(nums) - 1)

Complexity Analysis

Time Complexity: O(N log N) from merge sort.
Space Complexity: O(N) for temporary arrays used during merging, in addition to recursion stack space.

4. Maximum Product Subarray in an Array

Problem Description

Given an integer array nums, find the contiguous subarray that has the largest product and return that product.

The subarray must contain at least one element.

Intuition & Approach

Negative values make this problem different from maximum-sum subarray problems: multiplying by a negative value can turn a small negative product into the largest positive product. A zero also resets a product because no subarray extending through it can retain a non-zero product.

Scan from both directions while maintaining a running product:

Multiply the running products from the left and right by the current values.
Update the answer with both products.
Reset a running product to 1 after encountering zero.

Scanning in both directions ensures that a negative value at one boundary of the optimal subarray is handled correctly.

Example Walkthrough

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

The products of the relevant contiguous subarrays include 2 * 3 = 6 and (-2) * 4 = -8. The maximum product is achieved by [2, 3].

Output: 6

Python Solution

class Solution:
    def maxProduct(self, nums):
        max_product = float("-inf")
        left_prod, right_prod = 1, 1

        for index, el in enumerate(nums):
            left_prod = left_prod * el
            right_prod = right_prod * nums[len(nums) - index - 1]

            max_product = max(max_product, max(left_prod, right_prod))
            if left_prod == 0: left_prod = 1
            if right_prod == 0: right_prod = 1
                        
        return max_product

Complexity Analysis

Time Complexity: O(N) because the array is scanned once from both directions.
Space Complexity: O(1) auxiliary space.

5. Merge Two Sorted Arrays Without Extra Space

Problem Description

Given two sorted arrays nums1 and nums2, merge nums2 into nums1 so that nums1 becomes sorted in non-decreasing order.

The first array has enough empty space at the end to hold all elements from the second array. The parameters m and n specify the number of valid elements in nums1 and nums2, respectively.

Intuition & Approach

Use three pointers from the end of the arrays:

i points to the last valid element in nums1.
j points to the last element in nums2.
index points to the last available position in nums1.

Compare nums1[i] and nums2[j], placing the larger value at nums1[index]. Fill positions from right to left so that moving existing values never overwrites an unprocessed value. Once all elements from nums2 are placed, the merge is complete.

Example Walkthrough

Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3

Starting from the end, place 6, then 5, then compare 3 and 2 and place 3. Continue until all values from nums2 have been inserted.

Output: nums1 = [1, 2, 2, 3, 5, 6]

Python Solution

class Solution:
    def merge(self, nums1, m, nums2, n):
        i, j = m - 1, n - 1
        index = m + n - 1

        while j >= 0:
            if i >= 0 and nums1[i] >= nums2[j]:
                nums1[index] = nums1[i]
                i -= 1
                index -= 1
            else:
                nums1[index] = nums2[j]
                index -= 1
                j -= 1

Complexity Analysis

Time Complexity: O(M + N), where M and N are the numbers of valid elements in the two arrays.
Space Complexity: O(1) auxiliary space.