Number of Adjacent Elements With the Same Color

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        ans, nums, count = [], [0]*n, 0

        for i in range(len(queries)):
            index, color = queries[i][0], queries[i][1]

            if index-1 >= 0 and nums[index] != 0 and nums[index-1] == nums[index]:
                count -= 1
            if index+1 < n and nums[index] != 0 and nums[index+1] == nums[index]:
                count -= 1

            nums[index] = color

            if index-1 >= 0 and nums[index] != 0 and nums[index-1] == nums[index]:
                count += 1
            if index+1 < n and nums[index] != 0 and nums[index+1] == nums[index]:
                count += 1

            ans.append(count)

        return ans

10 Prerequisite LeetCode Problems

For “2672. Number of Adjacent Elements With the Same Color”, the following are a good preparation:

  1. “27. Remove Element” - This problem teaches how to manipulate arrays based on certain conditions, a skill that is necessary for the current problem.

  2. “485. Max Consecutive Ones” - This problem deals with finding consecutive elements in an array which is directly related to the current problem which requires finding adjacent elements with the same color.

  3. “283. Move Zeroes” - This problem provides practice for operations involving moving or shifting elements in an array.

  4. “561. Array Partition I” - This problem introduces the concept of pairings in an array which can be useful for understanding adjacency in arrays.

  5. “167. Two Sum II - Input array is sorted” - This problem introduces the concept of pairs with certain properties in an array, which can be beneficial for understanding how to deal with adjacent elements.

  6. “414. Third Maximum Number” - This problem can be beneficial in enhancing skills to handle and manipulate array elements based on their values, useful for coloring operations in the current problem.

  7. “217. Contains Duplicate” - This problem is about finding duplicates in an array, understanding this can help to grasp the concept of checking for identical adjacent elements in the current problem.

  8. “448. Find All Numbers Disappeared in an Array” - This problem can enhance the understanding of working with array indices and their values, relevant when considering indices of color operations in the current problem.

  9. “442. Find All Duplicates in an Array” - This problem introduces handling duplicates in an array, helping you understand the comparison of adjacent elements in the current problem.

  10. “645. Set Mismatch” - This problem is about finding the duplicate and missing number in an array. It helps you understand more about working with array values and their indices, useful when dealing with color changes at given indices.

These cover array manipulation, adjacency, and handling element properties, which are key to solving the “2672. Number of Adjacent Elements With the Same Color” problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def colorTheArray(n, queries):
    nums = [0]*n
    result = []
    c = 0

    for query in queries:
        index, color = query
        pre = nums[index - 1] if index > 0 else 0
        nex = nums[index + 1] if index < n-1 else 0

        if nums[index] and nums[index] == pre: 
            c -= 1
        if nums[index] and nums[index] == nex: 
            c -= 1
        nums[index] = color
        if nums[index] == pre: 
            c += 1
        if nums[index] == nex: 
            c += 1

        result.append(c)
    return result

There is a 0-indexed array nums of length n. Initially, all elements are uncolored (has a value of 0).

You are given a 2D integer array queries where queries[i] = [indexi, colori].

For each query, you color the index indexi with the color colori in the array nums.

Return an array answer of the same length as queries where answer[i] is the number of adjacent elements with the same color after the ith query.

More formally, answer[i] is the number of indices j, such that 0 <= j < n - 1 and nums[j] == nums[j + 1] and nums[j] != 0 after 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: Initially array nums = [0,0,0,0], where 0 denotes uncolored elements of the array.

  • After the 1st query nums = [2,0,0,0]. The count of adjacent elements with the same color is 0.
  • After the 2nd query nums = [2,2,0,0]. The count of adjacent elements with the same color is 1.
  • After the 3rd query nums = [2,2,0,1]. The count of adjacent elements with the same color is 1.
  • After the 4th query nums = [2,1,0,1]. The count of adjacent elements with the same color is 0.
  • After the 5th query nums = [2,1,1,1]. The count of adjacent elements with the same color is 2. Example 2:

Input: n = 1, queries = [[0,100000]] Output: [0] Explanation: Initially array nums = [0], where 0 denotes uncolored elements of the array.

  • After the 1st query nums = [100000]. The count of adjacent elements with the same color is 0.

Constraints:

1 <= n <= 105 1 <= queries.length <= 105 queries[i].length == 2 0 <= indexi <= n - 1 1 <= colori <= 105

Problem Classification

Analysis of the Problem Statement:

Domain Categorization: This problem falls under the ‘Data Structures and Algorithms’ domain. Specifically, it deals with the manipulation and analysis of arrays.

The ‘What’ Components:

  1. An initial 0-indexed array, nums, of length n, where all elements are uncolored (have a value of 0).
  2. A 2D integer array queries of size m, where queries[i] = [indexi, colori]. Each query instructs to color the indexi with the color colori in the array nums.
  3. The problem asks to return an array answer of the same length as queries where answer[i] is the number of adjacent elements with the same color after the ith query. The condition here is to count only those indices j (0 <= j < n - 1) such that nums[j] == nums[j + 1] and nums[j] != 0 after the ith query.

Problem Classification: This problem can be classified as a ‘Simulation’ problem. The problem simulates a set of operations (the queries) on an array, and then after each operation, it performs an evaluation (counting adjacent elements with the same color). The problem involves keeping track of states (the array after each coloring operation) and requires the use of arrays to keep track of these states and to store the queries.

Language Agnostic Coding Drills

  1. Concepts present in the code:

  • Variable Declaration: It’s one of the most basic concepts in any programming language. It’s about creating a variable and assigning a value to it. In the given code, variables like n, queries, nums, result, c, query, index, color, pre, and nex are declared.

  • List Initialization: In Python, list initialization is achieved using square brackets []. In this code, nums is initialized to a list of zeroes and result is an empty list.

  • Loops: In the code, a for loop is used to iterate over the queries list. Each iteration deconstructs a query into index and color.

  • Conditional Statements: if conditions are used in the code to check for specific conditions and run a piece of code only if that condition is true. For example, it’s used to check whether an index is within the bounds of a list before accessing the list element.

  • List indexing: Python lists are zero-indexed. In the code, indexing is used to access and update elements in the nums list.

  • Ternary Operator: The code uses ternary operators to assign a value to pre and nex based on whether index is within the bounds of nums.

  • Arithmetic Operations: The code performs arithmetic operations like addition and subtraction to update the variable c.

  • List appending: Python list method append() is used to add an item to the end of the list. In this code, it’s used to add the value of c to result in each iteration.

  1. Concepts in order of increasing difficulty:

  • Variable Declaration: The easiest concept, as it only requires knowing how to assign a value to a variable.

  • List Initialization: Easy, but requires understanding of the list data structure.

  • Arithmetic Operations: Basic arithmetic operations like addition and subtraction.

  • List indexing: Requires understanding of how indexing works in Python.

  • Conditional Statements: Requires logical thinking to construct the correct condition.

  • Loops: Requires understanding of how loops work and how to use them to iterate over a data structure.

  • Ternary Operator: Requires understanding of conditional expressions in Python.

  • List appending: Intermediate concept, involves adding items to a list in correct order.

  1. Problem-solving approach:

The solution to the problem involves iterating through each query and updating the nums list based on the index and color in the query.

The code maintains a counter c to keep track of the number of adjacent elements with the same color in nums. The counter is updated based on whether the color of nums[index] is equal to the color of its previous and next element.

After processing each query, the current value of c is appended to the result list. At the end of the loop, result will contain the number of adjacent elements with the same color after each query.

Targeted Drills in Python

  1. Python-based coding drills for each identified concept:
  • Variable Declaration:
1
2

# Declare a variable and assign a value to it
x = 5
  • List Initialization:
1
2
3
4
5

# Initialize a list with zeroes
nums = [0] * 5  # Output: [0, 0, 0, 0, 0]

# Initialize an empty list
result = []  # Output: []
  • Arithmetic Operations:
1
2
3
4
5

# Basic arithmetic operations
x = 5
y = 2
addition = x + y  # Output: 7
subtraction = x - y  # Output: 3
  • List indexing:
1
2
3
4
5
6
7

# Accessing and updating elements in a list
nums = [0, 1, 2, 3, 4]
first_element = nums[0]  # Output: 0
last_element = nums[-1]  # Output: 4

# Update an element in the list
nums[0] = 5  # Output: [5, 1, 2, 3, 4]
  • Conditional Statements:
1
2
3
4

# If condition in Python
x = 5
if x > 0:
    print("x is positive")  # Output: "x is positive"
  • Loops:
1
2
3

# A for loop in Python
for i in range(5):
    print(i)  # Output: 0 1 2 3 4
  • Ternary Operator:
1
2
3
4

# Ternary operator in Python
x = 5
message = "x is positive" if x > 0 else "x is non-positive"
print(message)  # Output: "x is positive"
  • List appending:
1
2
3

# Append an item to a list in Python
nums = [0, 1, 2, 3, 4]
nums.append(5)  # Output: [0, 1, 2, 3, 4, 5]
  1. Problem-specific concept:
  • Iterating over a list of queries and updating a list based on each query. This is essential for our problem as the solution involves processing a list of queries and updating the nums list based on each query. Here is a basic coding drill for this concept:
1
2
3
4
5
6
7
8

nums = [0, 0, 0, 0, 0]
queries = [[1, 2], [2, 3], [1, 1]]

for query in queries:
    index, color = query
    nums[index] = color  # Update nums based on the query

print(nums)  # Output: [0, 1, 3, 0, 0]
  1. To solve the initial problem, these drills can be integrated together in the following order:

  • Initialize the nums list and the result list.

  • Iterate over the queries list.

  • In each iteration, extract index and color from the current query.

  • Check the color of the previous and next element of nums[index] and update the counter c.

  • Update nums[index] with color and again check the color of the previous and next element and update c.

  • Append the current value of c to result.

  • At the end of the loop, result will contain the answer to our problem.