Press "Enter" to skip to content

Posts tagged as “easy”

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

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++

花花酱 LeetCode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

Given a string s containing only lower case English letters and the ‘?’ character, convert all the ‘?’ characters into lower case letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non ‘?’ characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for ‘?’.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Example 3:

Input: s = "j?qg??b"
Output: "jaqgacb"

Example 4:

Input: s = "??yw?ipkj?"
Output: "acywaipkja"

Constraints:

  • 1 <= s.length <= 100
  • s contains only lower case English letters and ‘?’.

Solution: Greedy

For each ?, find the first one among ‘abc’ that is not same as left or right.

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

C++

花花酱 LeetCode 1572. Matrix Diagonal Sum

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++

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

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

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++

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++

花花酱 LeetCode 1560. Most Visited Sector in a Circular Track

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The ith round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Example 1:

Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.

Example 2:

Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]

Example 3:

Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]

Constraints:

  • 2 <= n <= 100
  • 1 <= m <= 100
  • rounds.length == m + 1
  • 1 <= rounds[i] <= n
  • rounds[i] != rounds[i + 1] for 0 <= i < m

Solution: Simulation

Time complexity: O(m*n)
Space complexity: O(n)

C++