Posts tagged as “array”

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

}

};

花花酱 LeetCode 1909. Remove One Element to Make the Array Strictly Increasing

By zxi on December 24, 2021

Given a 0-indexed integer array nums, return true if it can be made strictly increasing after removing exactly one element, or false otherwise. If the array is already strictly increasing, return true.

The array nums is strictly increasing if nums[i - 1] < nums[i] for each index (1 <= i < nums.length).

Example 1:

Input: nums = [1,2,10,5,7]
Output: true
Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7].
[1,2,5,7] is strictly increasing, so return true.

Example 2:

Input: nums = [2,3,1,2]
Output: false
Explanation:
[3,1,2] is the result of removing the element at index 0.
[2,1,2] is the result of removing the element at index 1.
[2,3,2] is the result of removing the element at index 2.
[2,3,1] is the result of removing the element at index 3.
No resulting array is strictly increasing, so return false.

Example 3:

Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any element is [1,1].
[1,1] is not strictly increasing, so return false.

Constraints:

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

Solution 1: Brute Force

Enumerate the element to remove and check.

Time complexity: O(n²)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

bool canBeIncreasing(vector<int>& nums) {

const int n = nums.size();

auto check = [&](int k) {

vector<int> arr(nums);

arr.erase(begin(arr) + k);

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

if (arr[i] <= arr[i - 1]) return false;

return true;

};

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

if (check(i)) return true;

return false;

}

};

C++/O(1) Space

// Author: Huahua

class Solution {

public:

bool canBeIncreasing(vector<int>& nums) {

const int n = nums.size();

auto check = [&](int k) {

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

int j = (i - 1 == k) ? (i - 2) : (i - 1);

if (i != k && j >= 0 && nums[i] <= nums[j])

return false;

}

return true;

};

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

if (check(i)) return true;

return false;

}

};