Posts published in “Algorithms”

花花酱 LeetCode 1395. Count Number of Teams

By zxi on March 28, 2020

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

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

for (int j = i + 1; j < n; ++j)

for (int k = j + 1; k < n; ++k)

if (rating[i] < rating[j] && rating[j] < rating[k]

|| rating[i] > rating[j] && rating[j] > rating[k])

++ans;

return ans;

}

};

Solution 2: Math

For each soldier j, count how many soldiers on his left has smaller ratings as left[j], count how many soldiers his right side has larger ratings as right[j]

ans = sum(left[j] * right[j] + (j – left[j]) * (n – j – 1 * right[j])

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

C++

// Author: Huahua, 4 ms

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

for (int j = 0; j < n; ++j) {

int l = 0;

int r = 0;

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

if (rating[i] < rating[j]) ++l;

for (int k = j + 1; k < n; ++k)

if (rating[j] < rating[k]) ++r;

ans += (l * r) + (j - l) * (n - j - 1 - r);

}

return ans;

}

};

花花酱 LeetCode 1380. Lucky Numbers in a Matrix

By zxi on March 15, 2020

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]

Constraints:

m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5.
All elements in the matrix are distinct.

Solution: Pre-processing

Two pass. First pass, record the min val of each row, and max val of each column.
Second pass, identify lucky numbers.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> luckyNumbers (vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

vector<int> rows(m, INT_MAX);

vector<int> cols(n, INT_MIN);

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

for (int j = 0; j < n; ++j) {

rows[i] = min(rows[i], matrix[i][j]);

cols[j] = max(cols[j], matrix[i][j]);

}

vector<int> ans;

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

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

if (matrix[i][j] == rows[i] &&

matrix[i][j] == cols[j])

ans.push_back(matrix[i][j]);

return ans;

}

};

花花酱 LeetCode 240. Search a 2D Matrix II

By zxi on March 13, 2020

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Solution 1: Two Pointers

Start from first row + last column, if the current value is larger than target, –column; if smaller then ++row.

e.g.
1. r = 0, c = 4, v = 15, 15 > 5 => –c
2. r = 0, c = 3, v = 11, 11 > 5 => –c
3. r = 0, c = 2, v = 7, 7 > 5 => –c
4. r = 0, c = 1, v = 4, 4 < 5 => ++r
5. r = 1, c = 1, v = 5, 5 = 5, found it!

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

C++

// Author: Huahua

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty() || matrix[0].empty()) return false;

const int m = matrix.size();

const int n = matrix[0].size();

int r = 0;

int c = matrix[0].size() - 1;

while (r < m && c >= 0) {

if (matrix[r][c] == target) return true;

else if (matrix[r][c] > target) --c;

else ++r;

}

return false;

}

};

花花酱 LeetCode 229. Majority Element II

By zxi on March 13, 2020

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution: Boyer–Moore Voting Algorithm

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

C++

// Author: Huahua

class Solution {

public:

vector<int> majorityElement(vector<int>& nums) {

int n1 = 0;

int c1 = 0;

int n2 = 1;

int c2 = 0;

for (int num : nums) {

if (num == n1) {

++c1;

} else if (num == n2) {

++c2;

} else if (c1 == 0) {

n1 = num;

c1 = 1;

} else if (c2 == 0) {

n2 = num;

c2 = 1;

} else {

--c1;

--c2;

}

c1 = c2 = 0;

for (int num : nums) {

if (num == n1) ++c1;

else if (num == n2) ++c2;

}

const int c = nums.size() / 3;

vector<int> ans;

if (c1 > c) ans.push_back(n1);

if (c2 > c) ans.push_back(n2);

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def majorityElement(self, nums: List[int]) -> List[int]:

n1, c1, n2, c2 = 0, 0, 1, 0

for num in nums:

if num == n1: c1 += 1

elif num == n2: c2 += 1

elif c1 == 0: n1, c1 = num, 1

elif c2 == 0: n2, c2 = num, 1

else: c1, c2 = c1 - 1, c2 -1

c1, c2 = 0, 0

for num in nums:

if num == n1: c1 += 1

elif num == n2: c2 += 1

ans = []

if c1 > len(nums) // 3: ans.append(n1)

if c2 > len(nums) // 3: ans.append(n2)

return ans

花花酱 LeetCode 1375. Bulb Switcher III

By zxi on March 8, 2020

There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.

At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.

Return the number of moments in which all turned on bulbs are blue.

Example 1:

Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

Example 2:

Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).

Example 3:

Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.

Example 4:

Input: light = [2,1,4,3,6,5]
Output: 3

Example 5:

Input: light = [1,2,3,4,5,6]
Output: 6

Constraints:

n == light.length
1 <= n <= 5 * 10^4
light is a permutation of [1, 2, ..., n]

Solution

Track the right most light l_k, all turned-on lights are blue if and only if the right most one is k, and there are exact k lights on right now.

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

C++

// Author: Huahua

class Solution {

public:

int numTimesAllBlue(vector<int>& light) {

int ans = 0;

int right = 0;

for (int i = 0; i < light.size(); ++i) {

right = max(right, light[i]);

ans += right == i + 1;

}

return ans;

}

};

Posts published in “Algorithms”

花花酱 LeetCode 1395. Count Number of Teams

Solution 1: Brute Force

C++

Solution 2: Math

C++

花花酱 LeetCode 1380. Lucky Numbers in a Matrix

Solution: Pre-processing

C++

花花酱 LeetCode 240. Search a 2D Matrix II

Solution 1: Two Pointers

C++

花花酱 LeetCode 229. Majority Element II

Solution: Boyer–Moore Voting Algorithm

C++

Python3

Related Problem

花花酱 LeetCode 1375. Bulb Switcher III

Solution

C++