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] = [indexi, colori]. For the ith query:
colors[indexi] to colori.colors set to the same color (regardless of colori).Return an array answer of the same length as queries where answer[i] is the answer to the ith query.
Example 1:
Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
Output: [0,1,1,0,2]
Explanation:
Example 2:
Input: n = 1, queries = [[0,100000]]
Output: [0]
Explanation:
After the 1st query colors = [100000]. The count of adjacent pairs with the same color is 0.
Constraints:
1 <= n <= 1051 <= queries.length <= 105queries[i].length == 20 <= indexi <= n - 11 <= colori <= 105We iterate through each query, updating the color of the given index in the colors array. After each update, we check the color of the neighboring elements (left and right) to determine if there is an increase or decrease in the count of adjacent similar colors. This direct checking ensures we update our result efficiently.
The solution involves tracking the number of adjacent elements with the same color by iterating over the queries one at a time. For each query, we update the element at the specified index and adjust the count of similar adjacent pairs by checking both the left and right neighbors before and after the update.
C++
Java
Python
C#
JavaScript
Time Complexity: O(queriesSize) because we process each query individually.
Space Complexity: O(n) for the color array and result array.
This approach optimizes the process by using lazy initialization. Instead of resetting counts each time, it uses previous state data. Before updating an element, adjacent pairs are compared, and only necessary changes are tracked and updated in the adjacent count.
A more optimized way to manage color changes is implemented in this C solution by minimizing recalculations. Instead of recalculating entirely, only changes around the updated index are considered, thus saving computational resources.
C++
Java
Python
C#
JavaScript
Time Complexity: O(queriesSize) since each query is still processed separately.
Space Complexity: O(n) for storing the initial colors array.
| Approach | Complexity |
|---|---|
| Approach 1: Direct Updating with Adjacent Check | Time Complexity: Space Complexity: |
| Approach 2: Optimized Verification with Lazy Initialization | Time Complexity: Space Complexity: |
How to EASILY solve LeetCode problems • NeetCode • 427,736 views views
Watch 9 more video solutions →Practice Number of Adjacent Elements With the Same Color with our built-in code editor and test cases.
Practice on FleetCode