Posts published in “Array”

花花酱 LeetCode 1582. Special Positions in a Binary Matrix

By zxi on September 12, 2020

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],
              [0,0,1],
              [1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Example 2:

Input: mat = [[1,0,0],
              [0,1,0],
              [0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions.

Example 3:

Input: mat = [[0,0,0,1],
              [1,0,0,0],
              [0,1,1,0],
              [0,0,0,0]]
Output: 2

Example 4:

Input: mat = [[0,0,0,0,0],
              [1,0,0,0,0],
              [0,1,0,0,0],
              [0,0,1,0,0],
              [0,0,0,1,1]]
Output: 3

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is 0 or 1.

Solution: Sum for each row and column

Brute force:
Time complexity: O(R*C*(R+C))
Space complexity: O(1)

We can pre-compute the sums for each row and each column, ans = sum(mat[r][c] == 1 and rsum[r] == 1 and csum[c] == 1)

Time complexity: O(R*C)
Space complexity: O(R+C)

C++

class Solution {

public:

int numSpecial(vector<vector<int>>& mat) {

const int rows = mat.size();

const int cols = mat[0].size();

vector<int> rs(rows);

vector<int> cs(cols);

for (int r = 0; r < rows; ++r)

for (int c = 0; c < cols; ++c) {

rs[r] += mat[r][c];

cs[c] += mat[r][c];

}

int ans = 0;

for (int r = 0; r < rows; ++r)

for (int c = 0; c < cols; ++c)

ans += mat[r][c] && rs[r] == 1 && cs[c] == 1;

return ans;

}

};

花花酱 LeetCode 1572. Matrix Diagonal Sum

By zxi on September 5, 2020

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

Constraints:

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

Solution: Brute Force

Note: if n is odd, be careful not to double count the center one.

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int diagonalSum(vector<vector<int>>& mat) {

const int n = mat.size();

int ans = 0;

for (int i = 0; i < n; ++i)

ans += mat[i][i] + mat[i][n - i - 1];

if (n & 1) ans -= mat[n / 2][n / 2];

return ans;

}

};

花花酱 LeetCode 1566. Detect Pattern of Length M Repeated K or More Times

By zxi on August 29, 2020

Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.

A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

Constraints:

2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100

Solution 1: Brute Force

Time complexity: O(nmk)
Space complexity: O(1)

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

for (int i = 0; i + m * k <= n; ++i) {

bool valid = true;

for (int j = 1; j < k && valid; ++j)

for (int p = 0; p < m && valid; ++p)

if (arr[i + j * m + p] != arr[i + p])

valid = false;

if (valid) return true;

}

return false;

}

};

Solution 2: Shift and count

Since we need k consecutive subarrays, we can compare arr[i] with arr[i + m], if they are the same, increase the counter, otherwise reset the counter. If the counter reaches (k – 1) * m, it means we found k consecutive subarrays of length m.

ex1: arr = [1,2,4,4,4,4], m = 1, k = 3
i arr[i], arr[i + m] counter
0 1. 2. 0
0 2. 4. 0
0 4. 4. 1
0 4. 4. 2. <– found

ex2: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
i arr[i], arr[i + m] counter
0 1. 1. 1
0 2. 2. 2 <– found

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

int count = 0;

for (int i = 0; i + m < n; ++i) {

if (arr[i] == arr[i + m]) {

if (++count == (k - 1) * m) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1550. Three Consecutive Odds

By zxi on August 15, 2020

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

Solution: Counting

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

bool threeConsecutiveOdds(vector<int>& arr) {

int count = 0;

for (int x : arr) {

if (x & 1) {

if (++count == 3) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1535. Find the Winner of an Array Game

By zxi on August 1, 2020

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

Constraints:

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr contains distinct integers.
1 <= k <= 10^9

Solution 1: Simulation with a List

Observation : if k >= n – 1, ans = max(arr)

Time complexity: O(n+k)
Space complexity: O(n)

C++

class Solution {

public:

int getWinner(vector<int>& arr, int k) {

if (k >= arr.size()) return *max_element(begin(arr), end(arr));

int win = 0;

list<int> a(begin(arr), end(arr));

while (true) {

auto it0 = begin(a);

auto it1 = next(it0);

if (*it0 > *it1) {

a.splice(a.end(), a, it1);

++win;

} else {

swap(it0, it1);

a.splice(a.end(), a, it1);

win = 1;

}

if (win == k) return *it0;

}

return -1;

}

};

Solution 2: One pass

Since smaller numbers will be put to the end of the array, we must compare the rest of array before meeting those used numbers again. And the winner is monotonically increasing. So we can do it in one pass, just keep the largest number seen so far. If we reach to the end of the array, arr[0] will be max(arr) and it will always win no matter what k is.

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int getWinner(vector<int>& arr, int k) {

int winner = arr[0];

int win = 0;

for (int i = 1; i < arr.size(); ++i) {

if (arr[i] > winner) {

winner = arr[i];

win = 0;

}

if (++win == k) break;

}

return winner;

}

};

Java

class Solution {

public int getWinner(int[] arr, int k) {

int winner = arr[0];

int win = 0;

for (int i = 1; i < arr.length && win < k; ++i, ++win)

if (arr[i] > winner) {

winner = arr[i];

win = 0;

}

return winner;

}

Python3

class Solution:

def getWinner(self, arr: List[int], k: int) -> int:

winner = arr[0]

win = 0

for x in arr[1:]:

if x > winner:

winner, win = x, 0

win += 1

if win == k: break

return winner