Jobs

Interviews

Discussions

Array of Doubled Pairs

Medium

Asked by:

21 views

Topics:

ArraysGreedy AlgorithmsBit Manipulation

Given an integer array of even length arr, return true if it is possible to reorder arr such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2, or false otherwise.

Example 1:

Input: arr = [3,1,3,6]
Output: false

Example 2:

Input: arr = [2,1,2,6]
Output: false

Example 3:

Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Constraints:

2 <= arr.length <= 3 * 10⁴
arr.length is even.
-10⁵ <= arr[i] <= 10⁵

Try coding it in LeetCode

Array of Doubled Pairs

Medium

Asked by:

21 views

Topics:

ArraysGreedy AlgorithmsBit Manipulation

Example 1:

Input: arr = [3,1,3,6]
Output: false

Example 2:

Input: arr = [2,1,2,6]
Output: false

Example 3:

Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Constraints:

2 <= arr.length <= 3 * 10⁴
arr.length is even.
-10⁵ <= arr[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `arr` contain negative numbers, zeros, or floating-point numbers?
What is the expected return value if the input array cannot be rearranged to form doubled pairs? Should I return `false` or throw an exception?
Can the input array `arr` contain duplicate values, and if so, how should they be handled in forming the pairs?
Is the order of elements in the returned rearrangement significant, or can I return any valid rearrangement that satisfies the doubled pair condition?
What are the constraints on the size of the input array `arr`? Specifically, what is the maximum number of elements it can contain?

Brute Force Solution

Approach

The brute force approach for this problem is all about checking every possible pairing. We'll go through the numbers one by one and try to find a matching double for each. If we can find a match for every number, then we're good to go!

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Look through the rest of the list to see if its double exists.
If you find the double, mark both numbers as used so you don't use them again.
If you don't find the double, the list can't be arranged into doubled pairs, so you're done.
Repeat this process for the next unused number in the list.
Keep going until you've either matched every number or failed to find a double for a number.
If you successfully matched every number, then the list can be arranged into doubled pairs.

Code Implementation

def can_rearrange_to_doubled_pairs_brute_force(array):
    array_length = len(array)
    used_indices = [False] * array_length

    for i in range(array_length):
        # Skip already used numbers
        if used_indices[i]:
            continue

        number = array[i]
        double = 2 * number
        found_match = False

        for j in range(array_length):
            # Find the double of the current number.
            if not used_indices[j] and array[j] == double:
                used_indices[i] = True
                used_indices[j] = True
                found_match = True
                break

        # If we couldn't find a match, we can't form doubled pairs
        if not found_match:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force algorithm iterates through the array of n elements. For each element, it searches for its doubled counterpart in the remaining portion of the array. In the worst-case scenario, for each of the n elements, it may have to scan the rest of the array, which can take up to n-1 comparisons. This results in roughly n * (n-1) operations to find all the pairs, simplifying to O(n²).

Space Complexity

O(N) – The provided brute force approach requires marking numbers as 'used'. This could be implemented using an auxiliary boolean array of size N, where N is the number of elements in the input array, to keep track of which numbers have already been paired. Each element in this array corresponds to an element in the input, indicating whether it has been used. Therefore, the space complexity is O(N) due to this auxiliary data structure.

Optimal Solution

Approach

The goal is to figure out if you can pair up all the numbers in a list where each pair has one number that is exactly double the other. The best way to do this is to efficiently count how many of each number you have, and then cleverly use these counts to form pairs, starting with the smallest numbers.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the list.
Next, organize the unique numbers in increasing order.
Now, go through the numbers in order from smallest to largest.
For each number, check if we have enough of that number and its double to form the required number of pairs.
If we do, subtract the number of pairs formed from the counts of both the number and its double.
If at any point we don't have enough of both numbers to form pairs, then it's impossible to make all the doubled pairs. So we say it's not possible.
If we successfully go through all the numbers and use them all up by forming pairs, then it's possible to make the doubled pairs.

Code Implementation

def can_reorder_doubled(array): 
    number_counts = {}
    for number in array:
        number_counts[number] = number_counts.get(number, 0) + 1

    # Sort numbers to process smaller numbers first
    sorted_numbers = sorted(number_counts.keys())

    for number in sorted_numbers:
        if number_counts[number] == 0:
            continue

        double_number = 2 * number

        # Check if we have enough of the doubled number to form pairs
        if double_number not in number_counts or number_counts[number] > number_counts[double_number]:
            return False

        number_counts[double_number] -= number_counts[number]

    return True

Big(O) Analysis

Time Complexity

O(n log n) – Counting the occurrences of each number in the input array of size n takes O(n) time using a hash map. Sorting the unique numbers takes O(m log m) where m is the number of unique elements, and in the worst case m is n. Iterating through the sorted unique numbers and checking counts involves traversing at most n elements to form pairs, each step taking constant time. Therefore, the dominant factor is the sorting step, resulting in a time complexity of O(n log n).

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to count the occurrences of each number in the input array. In the worst case, where all numbers in the input array are unique, the hash map will store N key-value pairs, where N is the number of elements in the input array. Additionally, the algorithm sorts the unique numbers, which, depending on the sorting algorithm, could take O(N) auxiliary space in the worst case (e.g., merge sort). Therefore, the overall auxiliary space complexity is dominated by the hash map, resulting in O(N) space.

Edge Cases

Case	How to Handle
Null or undefined input array	Return false or throw an IllegalArgumentException as null input is invalid
Empty input array	Return true, as an empty array vacuously satisfies the condition
Array with odd number of elements	Return false immediately as it's impossible to form doubled pairs
Array contains negative numbers	The solution should handle negative numbers by considering both x and 2x when x is negative
Array contains zero(s)	Handle zeros carefully, ensuring each zero is paired with another zero
Array with a large number of identical values	Ensure the counting mechanism (e.g., HashMap) can accurately track occurrences without integer overflow
Integer overflow when calculating 2 * A[i]	Use a larger data type (e.g., long in Java) or check for overflow before multiplication
No valid doubled pairs exist	Return false when all elements have been processed and no valid arrangement is found

Null or undefined input array

How to Handle:

Return false or throw an IllegalArgumentException as null input is invalid

Empty input array

How to Handle:

Return true, as an empty array vacuously satisfies the condition

Array with odd number of elements

How to Handle:

Return false immediately as it's impossible to form doubled pairs

Array contains negative numbers

How to Handle:

The solution should handle negative numbers by considering both x and 2x when x is negative

Array contains zero(s)

How to Handle:

Handle zeros carefully, ensuring each zero is paired with another zero

Array with a large number of identical values

How to Handle:

Ensure the counting mechanism (e.g., HashMap) can accurately track occurrences without integer overflow

Integer overflow when calculating 2 * A[i]

How to Handle:

Use a larger data type (e.g., long in Java) or check for overflow before multiplication

No valid doubled pairs exist

How to Handle:

Return false when all elements have been processed and no valid arrangement is found

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `arr` contain negative numbers, zeros, or floating-point numbers?
What is the expected return value if the input array cannot be rearranged to form doubled pairs? Should I return `false` or throw an exception?
Can the input array `arr` contain duplicate values, and if so, how should they be handled in forming the pairs?
Is the order of elements in the returned rearrangement significant, or can I return any valid rearrangement that satisfies the doubled pair condition?
What are the constraints on the size of the input array `arr`? Specifically, what is the maximum number of elements it can contain?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Look through the rest of the list to see if its double exists.
If you find the double, mark both numbers as used so you don't use them again.
If you don't find the double, the list can't be arranged into doubled pairs, so you're done.
Repeat this process for the next unused number in the list.
Keep going until you've either matched every number or failed to find a double for a number.
If you successfully matched every number, then the list can be arranged into doubled pairs.

Code Implementation

def can_rearrange_to_doubled_pairs_brute_force(array):
    array_length = len(array)
    used_indices = [False] * array_length

    for i in range(array_length):
        # Skip already used numbers
        if used_indices[i]:
            continue

        number = array[i]
        double = 2 * number
        found_match = False

        for j in range(array_length):
            # Find the double of the current number.
            if not used_indices[j] and array[j] == double:
                used_indices[i] = True
                used_indices[j] = True
                found_match = True
                break

        # If we couldn't find a match, we can't form doubled pairs
        if not found_match:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the list.
Next, organize the unique numbers in increasing order.
Now, go through the numbers in order from smallest to largest.
For each number, check if we have enough of that number and its double to form the required number of pairs.
If we do, subtract the number of pairs formed from the counts of both the number and its double.
If at any point we don't have enough of both numbers to form pairs, then it's impossible to make all the doubled pairs. So we say it's not possible.
If we successfully go through all the numbers and use them all up by forming pairs, then it's possible to make the doubled pairs.

Code Implementation

def can_reorder_doubled(array): 
    number_counts = {}
    for number in array:
        number_counts[number] = number_counts.get(number, 0) + 1

    # Sort numbers to process smaller numbers first
    sorted_numbers = sorted(number_counts.keys())

    for number in sorted_numbers:
        if number_counts[number] == 0:
            continue

        double_number = 2 * number

        # Check if we have enough of the doubled number to form pairs
        if double_number not in number_counts or number_counts[number] > number_counts[double_number]:
            return False

        number_counts[double_number] -= number_counts[number]

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined input array	Return false or throw an IllegalArgumentException as null input is invalid
Empty input array	Return true, as an empty array vacuously satisfies the condition
Array with odd number of elements	Return false immediately as it's impossible to form doubled pairs
Array contains negative numbers	The solution should handle negative numbers by considering both x and 2x when x is negative
Array contains zero(s)	Handle zeros carefully, ensuring each zero is paired with another zero
Array with a large number of identical values	Ensure the counting mechanism (e.g., HashMap) can accurately track occurrences without integer overflow
Integer overflow when calculating 2 * A[i]	Use a larger data type (e.g., long in Java) or check for overflow before multiplication
No valid doubled pairs exist	Return false when all elements have been processed and no valid arrangement is found

Null or undefined input array

How to Handle:

Return false or throw an IllegalArgumentException as null input is invalid

Empty input array

How to Handle:

Return true, as an empty array vacuously satisfies the condition

Array with odd number of elements

How to Handle:

Return false immediately as it's impossible to form doubled pairs

Array contains negative numbers

How to Handle:

The solution should handle negative numbers by considering both x and 2x when x is negative

Array contains zero(s)

How to Handle:

Handle zeros carefully, ensuring each zero is paired with another zero

Array with a large number of identical values

How to Handle:

Ensure the counting mechanism (e.g., HashMap) can accurately track occurrences without integer overflow

Integer overflow when calculating 2 * A[i]

How to Handle:

Use a larger data type (e.g., long in Java) or check for overflow before multiplication

No valid doubled pairs exist

How to Handle:

Return false when all elements have been processed and no valid arrangement is found