Number of Adjacent Elements With the Same Color

Medium

Asked by:

81 views

Topics:

Arrays

You are given an integer n representing an array colors of length n where all elements are set to 0's meaning uncolored. You are also given a 2D integer array queries where queries[i] = [index_i, color_i]. For the i^th query:

Set colors[index_i] to color_i.
Count the number of adjacent pairs in colors which have the same color (regardless of color_i).

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

Example 1:

Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

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

Explanation:

Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.
After the 1^st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
After the 2^nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
After the 3^rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
After the 4^th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
After the 5^th query colors = [2,1,1,1]. The count of adjacent pairs with the same color is 2.

Example 2:

Input: n = 1, queries = [[0,100000]]

Output: [0]

Explanation:

After the 1^st query colors = [100000]. The count of adjacent pairs with the same color is 0.

Constraints:

1 <= n <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= index_i <= n - 1
1 <= color_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:

What are the constraints on the size of the input array `nums` and the number of queries?
What are the possible values (range and data type) for the colors in the `nums` array and the query colors? Can they be negative or zero?
If a query's index is out of bounds for the `nums` array, how should that be handled?
After the update, should I consider the updated element in `nums` when calculating adjacent elements with the same color for the current query's result?
Is the provided index in each query guaranteed to be a valid index within the bounds of the array at the time the query is processed?

Brute Force Solution

Approach

The basic idea is to try out every single possible color assignment for each position and count the adjacent elements with the same color for each of these assignments. We then record the number of adjacent elements with the same color after each change.

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

Start with the initial color assignment given.
Go through each position one by one.
For the current position, temporarily change its color to each of the possible color values.
After each color change, compare the colors of the current element with its neighbors (if any).
Count how many adjacent elements have the same color as the current element.
Record this count.
After trying all possible colors for the current position, move to the next position and repeat steps 3-6.
Continue this process until you have gone through all the positions.

Code Implementation

def number_of_adjacent_elements_with_same_color_brute_force(colors, number_of_colors):

    number_of_adjacent_elements_with_same_color_record = []

    # Iterate through each position
    for current_index in range(len(colors)):

        original_color = colors[current_index]

        # Try all possible colors for the current position
        for possible_color in range(1, number_of_colors + 1):

            colors[current_index] = possible_color

            adjacent_same_color_count = 0

            # Compare the current element with its left neighbor
            if current_index > 0:
                if colors[current_index] == colors[current_index - 1]:
                    adjacent_same_color_count += 1

            # Compare the current element with its right neighbor
            if current_index < len(colors) - 1:
                if colors[current_index] == colors[current_index + 1]:
                    adjacent_same_color_count += 1

            # Record the number of adjacent elements with the same color
            number_of_adjacent_elements_with_same_color_record.append(adjacent_same_color_count)

        # Restore the original color after trying all possible colors
        colors[current_index] = original_color

    return number_of_adjacent_elements_with_same_color_record

Big(O) Analysis

Time Complexity

O(n * k) – The algorithm iterates through each of the n positions in the input. For each position, it tries k possible color values. For each of these k color assignments, it compares the color of the current position with its (at most) two neighbors, taking constant time O(1). Therefore, the time complexity is proportional to n * k * O(1) which simplifies to O(n * k), where n is the number of positions and k is the number of possible colors.

Space Complexity

O(1) – The algorithm iterates through each position and temporarily changes its color, but it doesn't explicitly create any auxiliary data structures like lists, maps, or sets to store intermediate results. It only counts the number of adjacent elements with the same color after each change, storing at most a constant number of counts. Therefore, the space complexity is constant, independent of the input size N (where N represents the number of positions). This results in O(1) auxiliary space.

Optimal Solution

Approach

The goal is to efficiently count pairs of adjacent elements with the same color after each color update. The optimal approach avoids re-evaluating the entire structure after each update by focusing solely on the direct neighborhood around the modified element.

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

Initially, go through the entire sequence and count all adjacent elements that share the same color.
When a color is updated at a specific position, focus on the elements directly to the left and right of that position.
Before updating the color, check if the element to the left had the same color as the original element, and if so, decrease the overall count because that adjacency is now broken.
Do the same check for the element to the right; if it had the same color as the original, decrease the count.
Now, update the color of the element.
Check if the element to the left now has the same color as the newly updated element. If they match, increase the overall count.
Similarly, check if the element to the right now has the same color as the newly updated element. If they match, increase the overall count.
By only adjusting the count based on the immediate neighbors that changed due to the update, we efficiently maintain the correct count without re-evaluating everything.

Code Implementation

def count_adjacent_same_color(colors, updates):
    number_of_colors = len(colors)
    adjacent_same_color_count = 0

    for i in range(number_of_colors - 1):
        if colors[i] == colors[i + 1]:
            adjacent_same_color_count += 1

    results = []
    for index, new_color in updates:
        # Store the original color for comparison
        original_color = colors[index]

        # Decrement if left neighbor had same color
        if index > 0:
            if colors[index - 1] == original_color:
                adjacent_same_color_count -= 1

        # Decrement if right neighbor had same color
        if index < number_of_colors - 1:
            if colors[index + 1] == original_color:
                adjacent_same_color_count -= 1

        # Update color at index
        colors[index] = new_color

        # Increment if left neighbor now has same color
        if index > 0:
            if colors[index - 1] == new_color:
                adjacent_same_color_count += 1

        # Increment if right neighbor now has same color
        if index < number_of_colors - 1:
            if colors[index + 1] == new_color:
                adjacent_same_color_count += 1

        results.append(adjacent_same_color_count)

    return results

Big(O) Analysis

Time Complexity

O(n) – The initial counting of adjacent elements with the same color iterates through the entire input array of size n. Each update only considers the element at a specific position and its immediate left and right neighbors. Therefore, the update operations are constant time O(1). Since there are potentially n elements and initial count takes O(n), the dominant operation becomes the initial count, resulting in a time complexity of O(n).

Space Complexity

O(1) – The provided approach focuses on modifying the input array in-place and uses only a few constant space variables to store the current count of adjacent elements with the same color. The algorithm does not create any auxiliary data structures, such as lists, hash maps, or recursion stacks, whose size depends on the input size N. Therefore, the auxiliary space required is constant regardless of the input array size, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty nums array	Return an empty list or throw an IllegalArgumentException as there are no elements to process.
Null or empty queries array	Return an empty list as there are no updates to perform and thus no counts to calculate.
nums array with a single element	Return an empty list as there are no adjacent elements to compare, regardless of the queries.
Query index out of bounds for nums array	Throw an IndexOutOfBoundsException or return an error value to indicate invalid input.
Large nums array with a large number of queries (performance)	Optimize the update and count adjacent elements operation to avoid quadratic time complexity (e.g., O(1) update, O(1) count). Use appropriate data structures and algorithms to ensure efficient updates and counting.
All elements in nums array initially have the same color	The initial count of adjacent same-color elements should be nums.length - 1, and each query may either reduce or maintain the count.
Query color is the same as the current color at the index	The number of adjacent elements with the same color should be updated based on whether the new color matches adjacent elements.
Integer overflow when counting adjacent elements if nums.length is very large	Use a data type with sufficient capacity to store the count, such as long.

Null or empty nums array

How to Handle:

Return an empty list or throw an IllegalArgumentException as there are no elements to process.

Null or empty queries array

How to Handle:

Return an empty list as there are no updates to perform and thus no counts to calculate.

nums array with a single element

How to Handle:

Return an empty list as there are no adjacent elements to compare, regardless of the queries.

Query index out of bounds for nums array

How to Handle:

Throw an IndexOutOfBoundsException or return an error value to indicate invalid input.

Large nums array with a large number of queries (performance)

How to Handle:

Optimize the update and count adjacent elements operation to avoid quadratic time complexity (e.g., O(1) update, O(1) count). Use appropriate data structures and algorithms to ensure efficient updates and counting.

All elements in nums array initially have the same color

How to Handle:

The initial count of adjacent same-color elements should be nums.length - 1, and each query may either reduce or maintain the count.

Query color is the same as the current color at the index

How to Handle:

The number of adjacent elements with the same color should be updated based on whether the new color matches adjacent elements.

Integer overflow when counting adjacent elements if nums.length is very large

How to Handle:

Use a data type with sufficient capacity to store the count, such as long.