Posts tagged as “easy”

花花酱 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;

}

};

花花酱 LeetCode 1374. Generate a String With Characters That Have Odd Counts

By zxi on March 8, 2020

Given an integer n, return a string with n characters such that each character in such string occurs an odd number of times.

The returned string must contain only lowercase English letters. If there are multiples valid strings, return any of them.

Example 1:

Input: n = 4
Output: "pppz"
Explanation: "pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".

Example 2:

Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".

Example 3:

Input: n = 7
Output: "holasss"

Constraints:

1 <= n <= 500

Solution: Greedy

if n is odd, return n ‘a’s.
otherwise, return n -1 ‘a’s and 1 ‘b’

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

C++

// Author: Huahua

class Solution {

public:

string generateTheString(int n) {

return n & 1 ? string(n, 'a') : string(n - 1, 'a') + "b";

}

};

Python3

# Author: Huahua

class Solution:

def generateTheString(self, n: int) -> str:

ans = ['a'] * n if n % 2 == 1 else ['a'] * (n - 1) + ['b']

return ''.join(ans)

花花酱 LeetCode 1370. Increasing Decreasing String

By zxi on March 7, 2020

Given a string s. You should re-order the string using the following algorithm:

Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Example 3:

Input: s = "leetcode"
Output: "cdelotee"

Example 4:

Input: s = "ggggggg"
Output: "ggggggg"

Example 5:

Input: s = "spo"
Output: "ops"

Constraints:

1 <= s.length <= 500
s contains only lower-case English letters.

Solution: Counting frequency of each character

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

C++

// Author: Huahua

class Solution {

public:

string sortString(string s) {

vector<int> count(26);

for (char c : s) ++count[c - 'a'];

string ans;

while (ans.length() != s.length()) {

for (char c = 'a'; c <= 'z'; ++c)

if (--count[c - 'a'] >= 0)

ans += c;

for (char c = 'z'; c >= 'a'; --c)

if (--count[c - 'a'] >= 0)

ans += c;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def sortString(self, s: str) -> str:

seq = string.ascii_lowercase + string.ascii_lowercase[::-1]

count = collections.Counter(s)

ans = ""

while len(ans) != len(s):

for c in seq:

if count[c] > 0:

ans += c

count[c] -= 1

return ans