Array
Description
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 :
Set colors[indexi ]
to colori
.
Count adjacent pairs in 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:
Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.
After the 1st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
After the 2nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
After the 3rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
After the 4th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
After the 5th 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 1st query colors = [100000]. The count of adjacent pairs 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
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def colorTheArray ( self , n : int , queries : List [ List [ int ]]) -> List [ int ]:
nums = [ 0 ] * n
ans = [ 0 ] * len ( queries )
x = 0
for k , ( i , c ) in enumerate ( queries ):
if i > 0 and nums [ i ] and nums [ i - 1 ] == nums [ i ]:
x -= 1
if i < n - 1 and nums [ i ] and nums [ i + 1 ] == nums [ i ]:
x -= 1
if i > 0 and nums [ i - 1 ] == c :
x += 1
if i < n - 1 and nums [ i + 1 ] == c :
x += 1
ans [ k ] = x
nums [ i ] = c
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public int [] colorTheArray ( int n , int [][] queries ) {
int m = queries . length ;
int [] nums = new int [ n ] ;
int [] ans = new int [ m ] ;
for ( int k = 0 , x = 0 ; k < m ; ++ k ) {
int i = queries [ k ][ 0 ] , c = queries [ k ][ 1 ] ;
if ( i > 0 && nums [ i ] > 0 && nums [ i - 1 ] == nums [ i ] ) {
-- x ;
}
if ( i < n - 1 && nums [ i ] > 0 && nums [ i + 1 ] == nums [ i ] ) {
-- x ;
}
if ( i > 0 && nums [ i - 1 ] == c ) {
++ x ;
}
if ( i < n - 1 && nums [ i + 1 ] == c ) {
++ x ;
}
ans [ k ] = x ;
nums [ i ] = c ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 class Solution {
public :
vector < int > colorTheArray ( int n , vector < vector < int >>& queries ) {
vector < int > nums ( n );
vector < int > ans ;
int x = 0 ;
for ( auto & q : queries ) {
int i = q [ 0 ], c = q [ 1 ];
if ( i > 0 && nums [ i ] > 0 && nums [ i - 1 ] == nums [ i ]) {
-- x ;
}
if ( i < n - 1 && nums [ i ] > 0 && nums [ i + 1 ] == nums [ i ]) {
-- x ;
}
if ( i > 0 && nums [ i - 1 ] == c ) {
++ x ;
}
if ( i < n - 1 && nums [ i + 1 ] == c ) {
++ x ;
}
ans . push_back ( x );
nums [ i ] = c ;
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 func colorTheArray ( n int , queries [][] int ) ( ans [] int ) {
nums := make ([] int , n )
x := 0
for _ , q := range queries {
i , c := q [ 0 ], q [ 1 ]
if i > 0 && nums [ i ] > 0 && nums [ i - 1 ] == nums [ i ] {
x --
}
if i < n - 1 && nums [ i ] > 0 && nums [ i + 1 ] == nums [ i ] {
x --
}
if i > 0 && nums [ i - 1 ] == c {
x ++
}
if i < n - 1 && nums [ i + 1 ] == c {
x ++
}
ans = append ( ans , x )
nums [ i ] = c
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 function colorTheArray ( n : number , queries : number [][]) : number [] {
const nums : number [] = new Array ( n ). fill ( 0 );
const ans : number [] = [];
let x = 0 ;
for ( const [ i , c ] of queries ) {
if ( i > 0 && nums [ i ] > 0 && nums [ i - 1 ] == nums [ i ]) {
-- x ;
}
if ( i < n - 1 && nums [ i ] > 0 && nums [ i + 1 ] == nums [ i ]) {
-- x ;
}
if ( i > 0 && nums [ i - 1 ] == c ) {
++ x ;
}
if ( i < n - 1 && nums [ i + 1 ] == c ) {
++ x ;
}
ans . push ( x );
nums [ i ] = c ;
}
return ans ;
}
GitHub