Jobs

Interviews

Discussions

Shortest Distance to Target Color

Medium

Asked by:

11 views

Topics:

ArraysBinary Search

You are given an array of integers colors, in which each element is either 0, 1 or 2. You are also given some queries. Each query consists of two integers index and color. For each query, find the shortest distance from the given index to a cell of the given color. If there is no such color in the array, return -1.

Return an array ans of the same length as queries, where ans[i] is the answer to the i^th query.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
Closest distance from index 1 to color 3 is 3.
Closest distance from index 2 to color 2 is 0.
Closest distance from index 6 to color 1 is 3.

Example 2:

Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no color 3 in the array colors.

Constraints:

1 <= colors.length <= 5 * 10⁴
0 <= colors[i] <= 2
1 <= queries.length <= 10⁴
queries[i].length == 2
0 <= queries[i][0] < colors.length
0 <= queries[i][1] <= 2

Try coding it in LeetCode

Shortest Distance to Target Color

Medium

Asked by:

11 views

Topics:

ArraysBinary Search

Return an array ans of the same length as queries, where ans[i] is the answer to the i^th query.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
Closest distance from index 1 to color 3 is 3.
Closest distance from index 2 to color 2 is 0.
Closest distance from index 6 to color 1 is 3.

Example 2:

Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no color 3 in the array colors.

Constraints:

1 <= colors.length <= 5 * 10⁴
0 <= colors[i] <= 2
1 <= queries.length <= 10⁴
queries[i].length == 2
0 <= queries[i][0] < colors.length
0 <= queries[i][1] <= 2

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:

What are the possible values for colors in the `colors` array? Are they guaranteed to be 1, 2, or 3, or could there be other integer values?
What is the expected return value if a given target color does not exist in the `colors` array?
What are the constraints on the length of the `colors` array?
Can the same index in the `colors` array contain multiple of the target color? Or should I treat each index as having only a single color?
Is the `index` argument guaranteed to be within the bounds of the `colors` array?

Brute Force Solution

Approach

The brute force method means we will check every possible distance for each position. We will look at every possible position around the target position and compute the distances until we find a color match.

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

For each position, look at the positions immediately to the left and right.
Check the color at these positions, if either matches our target color, record the distance of 1.
If we didn't find a match, expand our search by one position in both directions, checking those positions.
Keep expanding our search range outward, one position at a time on each side.
Stop when you find a position matching the target color. The number of steps you took to find it is the shortest distance.

Code Implementation

def shortest_distance_brute_force(colors, target_color): 
    results = []
    for start_position in range(len(colors)): 
        distance = 1
        found = False

        # If the starting position is already the target color, the distance is zero.
        if colors[start_position] == target_color:
            results.append(0)
            continue

        while not found:
            left_index = start_position - distance
            right_index = start_position + distance

            # Check left index
            if left_index >= 0:

                # Check if the color matches at the left index
                if colors[left_index] == target_color:
                    results.append(distance)
                    found = True
                    continue

            # Check right index
            if right_index < len(colors):

                # Check if the color matches at the right index
                if colors[right_index] == target_color:
                    results.append(distance)
                    found = True
                    continue

            #If neither left or right finds target, increase search radius.
            distance += 1

            #If no target is found, distance becomes array bounds.
            if left_index < 0 and right_index >= len(colors):
                results.append(-1)
                found = True

    return results

Big(O) Analysis

Time Complexity

O(n²) – For each of the n positions in the array, the algorithm expands its search outward until it finds the target color. In the worst case, for each position, the algorithm might need to search up to n/2 positions to the left and n/2 positions to the right to find the nearest target color. Thus, for each of the n positions, we perform a search that, in the worst case, takes approximately n steps. This results in approximately n * n/2 operations. Simplifying this expression, the time complexity is O(n²).

Space Complexity

O(1) – The brute force method described iterates outwards from each position to find the nearest target color. While the algorithm searches for the target, it primarily uses a few integer variables to store the current left and right search positions and potentially the minimum distance found so far. The number of positions checked does not require storing intermediate results in any data structure that scales with the size of the input array. Therefore, the auxiliary space used by this algorithm is constant, irrespective of the input size N (the length of the input array).

Optimal Solution

Approach

The most efficient way to find the shortest distance is to remember the locations of each color as we go. Then, for each spot, we can quickly check which color is closest by comparing distances to the nearest locations of each target color.

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

First, find and save the positions of all the places that have color '1', all the places that have color '2', and all the places that have color '3'.
Now, for each spot in the list, figure out which color is the closest.
To do this, for each spot, find the closest location of color '1', the closest location of color '2', and the closest location of color '3'.
Choose the smallest of those distances; that's the shortest distance to any of the target colors from that spot.
Repeat this for every spot in the list, and you'll have the shortest distance to a target color for each one.

Code Implementation

def shortest_distance_to_target_color(colors, queries):
    color1_indices = []
    color2_indices = []
    color3_indices = []

    # Store indices of each color
    for index, color in enumerate(colors):
        if color == 1:
            color1_indices.append(index)
        elif color == 2:
            color2_indices.append(index)
        else:
            color3_indices.append(index)

    result = []
    for query_index, target_color in queries:
        # Find closest index for target color
        if target_color == 1:
            indices = color1_indices
        elif target_color == 2:
            indices = color2_indices
        else:
            indices = color3_indices

        min_distance = float('inf')
        if not indices:
            result.append(-1)
            continue

        # Calculate shortest distance
        for index_value in indices:
            distance = abs(index_value - query_index)
            min_distance = min(min_distance, distance)

        result.append(min_distance)

    return result

Big(O) Analysis

Time Complexity

O(n) – First, the algorithm iterates through the input array of size n to store the indices of each color (1, 2, and 3). This takes O(n) time. Then, for each of the n locations in the input array, the algorithm finds the minimum distance to the nearest color 1, color 2, and color 3. Finding the nearest color for a specific location involves iterating through the stored indices of each color which, in the worst case, is still bounded by O(n). However because the creation of the color index lists dominates the runtime, especially when calculating for all colors simultaneously, the overall time complexity is O(n).

Space Complexity

O(N) – The provided solution requires storing the indices of each color (1, 2, and 3). In the worst-case scenario, one color might appear at almost every index in the input array, leading to lists of indices that could grow linearly with the input size N, where N is the number of elements in the input array. Therefore, we could have up to three lists, each potentially of size close to N, to store the positions of each color. Consequently, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty colors array	Return an empty result array since there are no colors to check.
Empty queries array	Return an empty result array as there are no queries to process.
No occurrence of the target color in the colors array	Return -1 for that query since the target color is not present.
Large colors array with few target color occurrences, leading to potentially long search	Binary search should be used for optimal lookup performance after pre-processing and storing the target color indices.
All elements in the colors array are the same color (the target color)	All query results will be 0, since the nearest color is always the current index.
Query index is at the very beginning or very end of the colors array	Handle boundary conditions correctly when calculating distances.
Integer overflow when calculating distances for very large arrays	Ensure that the data type used for distance calculations (e.g., int) can accommodate large differences in indices, or use long if necessary.
Query index out of bounds	Return an appropriate error value or throw an exception if the query index is outside the valid range [0, colors.length - 1].

Empty colors array

How to Handle:

Return an empty result array since there are no colors to check.

Empty queries array

How to Handle:

Return an empty result array as there are no queries to process.

No occurrence of the target color in the colors array

How to Handle:

Return -1 for that query since the target color is not present.

Large colors array with few target color occurrences, leading to potentially long search

How to Handle:

Binary search should be used for optimal lookup performance after pre-processing and storing the target color indices.

All elements in the colors array are the same color (the target color)

How to Handle:

All query results will be 0, since the nearest color is always the current index.

Query index is at the very beginning or very end of the colors array

How to Handle:

Handle boundary conditions correctly when calculating distances.

Integer overflow when calculating distances for very large arrays

How to Handle:

Ensure that the data type used for distance calculations (e.g., int) can accommodate large differences in indices, or use long if necessary.

Query index out of bounds

How to Handle:

Return an appropriate error value or throw an exception if the query index is outside the valid range [0, colors.length - 1].

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:

What are the possible values for colors in the `colors` array? Are they guaranteed to be 1, 2, or 3, or could there be other integer values?
What is the expected return value if a given target color does not exist in the `colors` array?
What are the constraints on the length of the `colors` array?
Can the same index in the `colors` array contain multiple of the target color? Or should I treat each index as having only a single color?
Is the `index` argument guaranteed to be within the bounds of the `colors` array?

Brute Force Solution

Approach

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

For each position, look at the positions immediately to the left and right.
Check the color at these positions, if either matches our target color, record the distance of 1.
If we didn't find a match, expand our search by one position in both directions, checking those positions.
Keep expanding our search range outward, one position at a time on each side.
Stop when you find a position matching the target color. The number of steps you took to find it is the shortest distance.

Code Implementation

def shortest_distance_brute_force(colors, target_color): 
    results = []
    for start_position in range(len(colors)): 
        distance = 1
        found = False

        # If the starting position is already the target color, the distance is zero.
        if colors[start_position] == target_color:
            results.append(0)
            continue

        while not found:
            left_index = start_position - distance
            right_index = start_position + distance

            # Check left index
            if left_index >= 0:

                # Check if the color matches at the left index
                if colors[left_index] == target_color:
                    results.append(distance)
                    found = True
                    continue

            # Check right index
            if right_index < len(colors):

                # Check if the color matches at the right index
                if colors[right_index] == target_color:
                    results.append(distance)
                    found = True
                    continue

            #If neither left or right finds target, increase search radius.
            distance += 1

            #If no target is found, distance becomes array bounds.
            if left_index < 0 and right_index >= len(colors):
                results.append(-1)
                found = True

    return results

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find and save the positions of all the places that have color '1', all the places that have color '2', and all the places that have color '3'.
Now, for each spot in the list, figure out which color is the closest.
To do this, for each spot, find the closest location of color '1', the closest location of color '2', and the closest location of color '3'.
Choose the smallest of those distances; that's the shortest distance to any of the target colors from that spot.
Repeat this for every spot in the list, and you'll have the shortest distance to a target color for each one.

Code Implementation

def shortest_distance_to_target_color(colors, queries):
    color1_indices = []
    color2_indices = []
    color3_indices = []

    # Store indices of each color
    for index, color in enumerate(colors):
        if color == 1:
            color1_indices.append(index)
        elif color == 2:
            color2_indices.append(index)
        else:
            color3_indices.append(index)

    result = []
    for query_index, target_color in queries:
        # Find closest index for target color
        if target_color == 1:
            indices = color1_indices
        elif target_color == 2:
            indices = color2_indices
        else:
            indices = color3_indices

        min_distance = float('inf')
        if not indices:
            result.append(-1)
            continue

        # Calculate shortest distance
        for index_value in indices:
            distance = abs(index_value - query_index)
            min_distance = min(min_distance, distance)

        result.append(min_distance)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty colors array	Return an empty result array since there are no colors to check.
Empty queries array	Return an empty result array as there are no queries to process.
No occurrence of the target color in the colors array	Return -1 for that query since the target color is not present.
Large colors array with few target color occurrences, leading to potentially long search	Binary search should be used for optimal lookup performance after pre-processing and storing the target color indices.
All elements in the colors array are the same color (the target color)	All query results will be 0, since the nearest color is always the current index.
Query index is at the very beginning or very end of the colors array	Handle boundary conditions correctly when calculating distances.
Integer overflow when calculating distances for very large arrays	Ensure that the data type used for distance calculations (e.g., int) can accommodate large differences in indices, or use long if necessary.
Query index out of bounds	Return an appropriate error value or throw an exception if the query index is outside the valid range [0, colors.length - 1].

Empty colors array

How to Handle:

Return an empty result array since there are no colors to check.

Empty queries array

How to Handle:

Return an empty result array as there are no queries to process.

No occurrence of the target color in the colors array

How to Handle:

Return -1 for that query since the target color is not present.

Large colors array with few target color occurrences, leading to potentially long search

How to Handle:

Binary search should be used for optimal lookup performance after pre-processing and storing the target color indices.

All elements in the colors array are the same color (the target color)

How to Handle:

All query results will be 0, since the nearest color is always the current index.

Query index is at the very beginning or very end of the colors array

How to Handle:

Handle boundary conditions correctly when calculating distances.

Integer overflow when calculating distances for very large arrays

How to Handle:

Ensure that the data type used for distance calculations (e.g., int) can accommodate large differences in indices, or use long if necessary.

Query index out of bounds

How to Handle:

Return an appropriate error value or throw an exception if the query index is outside the valid range [0, colors.length - 1].