Posts published in “Array”

花花酱 LeetCode 2148. Count Elements With Strictly Smaller and Greater Elements

By zxi on February 4, 2022

Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element appear in nums.

Example 1:

Input: nums = [11,7,2,15]
Output: 2
Explanation: The element 7 has the element 2 strictly smaller than it and the element 11 strictly greater than it.
Element 11 has element 7 strictly smaller than it and element 15 strictly greater than it.
In total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.

Example 2:

Input: nums = [-3,3,3,90]
Output: 2
Explanation: The element 3 has the element -3 strictly smaller than it and the element 90 strictly greater than it.
Since there are two elements with the value 3, in total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.

Constraints:

1 <= nums.length <= 100
-10⁵ <= nums[i] <= 10⁵

Solution: Min / Max elements

Find min and max of the array, count elements other than those two.

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

C++

// Author: Huahua

class Solution {

public:

int countElements(vector<int>& nums) {

auto [it1, it2] = minmax_element(begin(nums), end(nums));

return count_if(begin(nums), end(nums), [lo=*it1, hi=*it2](int x) {

return x != lo && x != hi;

});

}

};

花花酱 LeetCode 1991. Find the Middle Index in Array

By zxi on December 31, 2021

Given a 0-indexed integer array nums, find the leftmost middleIndex (i.e., the smallest amongst all the possible ones).

A middleIndex is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].

If middleIndex == 0, the left side sum is considered to be 0. Similarly, if middleIndex == nums.length - 1, the right side sum is considered to be 0.

Return the leftmost middleIndex that satisfies the condition, or -1 if there is no such index.

Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4

Example 2:

Input: nums = [1,-1,4]
Output: 2
Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0

Example 3:

Input: nums = [2,5]
Output: -1
Explanation: There is no valid middleIndex.

Constraints:

1 <= nums.length <= 100
-1000 <= nums[i] <= 1000

Solution: Pre-compute + prefix sum

Pre-compute the sum of entire array. We scan the array and accumulate prefix sum and we can compute the sum of the rest of array.

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

C++

// Author: Huahua

class Solution {

public:

int findMiddleIndex(vector<int>& nums) {

int sum = accumulate(begin(nums), end(nums), 0);

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

if (cur == sum - cur - nums[i]) return i;

cur += nums[i];

}

return -1;

}

};

花花酱 LeetCode 1985. Find the Kth Largest Integer in the Array

By zxi on December 31, 2021

You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.

Return the string that represents the k^th largest integer in nums.

Note: Duplicate numbers should be counted distinctly. For example, if nums is ["1","2","2"], "2" is the first largest integer, "2" is the second-largest integer, and "1" is the third-largest integer.

Example 1:

Input: nums = ["3","6","7","10"], k = 4
Output: "3"
Explanation:
The numbers in nums sorted in non-decreasing order are ["3","6","7","10"].
The 4^th largest integer in nums is "3".

Example 2:

Input: nums = ["2","21","12","1"], k = 3
Output: "2"
Explanation:
The numbers in nums sorted in non-decreasing order are ["1","2","12","21"].
The 3^rd largest integer in nums is "2".

Example 3:

Input: nums = ["0","0"], k = 2
Output: "0"
Explanation:
The numbers in nums sorted in non-decreasing order are ["0","0"].
The 2^nd largest integer in nums is "0".

Constraints:

1 <= k <= nums.length <= 10⁴
1 <= nums[i].length <= 100
nums[i] consists of only digits.
nums[i] will not have any leading zeros.

Solution: nth_element / quick selection

Use std::nth_element to find the k-th largest element. When comparing two strings, compare their lengths first and compare their content if they have the same length.

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

C++

// Author: Huahua

class Solution {

public:

string kthLargestNumber(vector<string>& nums, int k) {

nth_element(begin(nums), begin(nums) + k - 1, end(nums), [](const auto& a, const auto& b) {

return a.length() == b.length() ? a > b : a.length() > b.length();

});

return nums[k - 1];

}

};

花花酱 LeetCode 1929. Concatenation of Array

By zxi on December 30, 2021

Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).

Specifically, ans is the concatenation of two nums arrays.

Return the array ans.

Example 1:

Input: nums = [1,2,1]
Output: [1,2,1,1,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]

Example 2:

Input: nums = [1,3,2,1]
Output: [1,3,2,1,1,3,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]

Constraints:

n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000

Solution: Pre-allocation

Pre-allocate an array of length 2 * n.
ans[i] = nums[i % n]

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

vector<int> ans(2 * n);

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

ans[i] = nums[i % n];

return ans;

}

};

花花酱 LeetCode 1920. Build Array from Permutation

By zxi on December 25, 2021

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

Example 1:

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows: 
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

Example 2:

Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
The elements in nums are distinct.

Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?

Solution 1: Straight forward

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans(nums);

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

ans[i] = nums[nums[i]];

return ans;

}

};

Solution 2: Follow up: Inplace Encoding

Since nums[i] <= 1000, we can use low 16 bit to store the original value and high 16 bit for new value.

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

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

nums[i] |= (nums[nums[i]] & 0xffff) << 16;

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

nums[i] >>= 16;

return nums;

}

};