Posts tagged as “easy”

花花酱 LeetCode 1399. Count Largest Group

By zxi on April 4, 2020

Given an integer n. Each number from 1 to n is grouped according to the sum of its digits.

Return how many groups have the largest size.

Example 1:

Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.

Example 2:

Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

Example 3:

Input: n = 15
Output: 6

Example 4:

Input: n = 24
Output: 5

Constraints:

1 <= n <= 10^4

Solution: HashTable

Time complexity: O(nlogn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int countLargestGroup(int n) {

vector<int> c(37); // max sum is 9+9+9+9 = 36

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

int x = i;

int sum = 0;

while (x) {

sum += x % 10;

x /= 10;

}

++c[sum];

}

return count(begin(c), end(c), *max_element(begin(c), end(c)));

}

};

花花酱 LeetCode 1394. Find Lucky Integer in an Array

By zxi on March 28, 2020

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value.

Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.

Example 1:

Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Example 2:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

Example 3:

Input: arr = [2,2,2,3,3]
Output: -1
Explanation: There are no lucky numbers in the array.

Example 4:

Input: arr = [5]
Output: -1

Example 5:

Input: arr = [7,7,7,7,7,7,7]
Output: 7

Constraints:

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

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int findLucky(vector<int>& arr) {

unordered_map<int, int> freq;

for (int x : arr) ++freq[x];

int ans = -1;

for (const auto& [key, count] : freq)

if (key == count) ans = max(ans, key);

return ans;

}

};

花花酱 LeetCode 1389. Create Target Array in the Given Order

By zxi on March 22, 2020

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

Initially target array is empty.
From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3:

Input: nums = [1], index = [0]
Output: [1]

Constraints:

1 <= nums.length, index.length <= 100
nums.length == index.length
0 <= nums[i] <= 100
0 <= index[i] <= i

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {

vector<int> target;

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

target.insert(begin(target) + index[i], nums[i]);

return target;

}

};

花花酱 LeetCode 1385. Find the Distance Value Between Two Arrays

By zxi on March 21, 2020

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1:

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1

Constraints:

1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100

Solution 1: All pairs

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

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

int ans = 0;

for (int x : arr1) {

bool flag = true;

for (int y : arr2)

if (abs(x - y) <= d) {

flag = false;

break;

}

ans += flag;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:

return sum(all(abs(x - y) > d for y in arr2) for x in arr1)

Solution 2: Two Pointers

Sort arr1 in ascending order and sort arr2 in descending order.
Time complexity: O(mlogm + nlogn + m + n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

sort(begin(arr1), end(arr1));

sort(rbegin(arr2), rend(arr2));

int ans = 0;

for (int a : arr1) {

while (arr2.size() && arr2.back() < a - d)

arr2.pop_back();

ans += arr2.empty() || arr2.back() > a + d;

}

return ans;

}

};

Solution 3: Binary Search

Sort arr2 in ascending order. and do two binary searches for each element to determine the range of [a-d, a+d], if that range is empty we increase the counter

Time complexity: O(mlogm + nlogm)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

sort(begin(arr2), end(arr2));

int ans = 0;

for (int a : arr1) {

auto it1 = lower_bound(begin(arr2), end(arr2), a - d);

auto it2 = upper_bound(begin(arr2), end(arr2), a + d);

if (it1 == it2) ++ans;

}

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;

}

};