Posts published in “Array”

花花酱 LeetCode 1480. Running Sum of 1d Array

By zxi on June 14, 2020

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Constraints:

1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6

Solution

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans(nums);

for (int i = 1; i < ans.size(); ++i)

ans[i] += ans[i - 1];

return ans;

}

};

花花酱 LeetCode 1471. The k Strongest Values in an Array

By zxi on June 6, 2020

Given an array of integers arr and an integer k.

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.

Example 4:

Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]

Example 5:

Input: arr = [-7,22,17,3], k = 2
Output: [22,17]

Constraints:

1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length

Solution 1: quick selection + sort

Step 1: find the median element m
Step 2: Sort the array according to m
Step 3: output the first k elements of the sorted array.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getStrongest(vector<int>& arr, int k) {

const int n = arr.size();

const int i = (n - 1) / 2;

// sort(begin(arr), end(arr));

nth_element(begin(arr), begin(arr) + i, end(arr));

const int m = arr[i];

sort(begin(arr), end(arr), [&](const int x, const int y) {

return abs(x - m) != abs(y - m) ? abs(x - m) > abs(y - m) : x > y;

});

return {begin(arr), begin(arr) + k};

}

};

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

By zxi on May 31, 2020

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

Solution 1: Sort

We want to find the largest and second largest elements.

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

return (nums[0] - 1) * (nums[1] - 1);

}

};

Solution 2: Without sorting

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

int m1 = 0;

int m2 = 0;

for (int n : nums) {

if (n > m1) {

m2 = m1;

m1 = n;

} else if (n > m2) {

m2 = n;

}

return (m1 - 1) * (m2 - 1);

}

};

花花酱 LeetCode 1460. Make Two Arrays Equal by Reversing Sub-arrays

By zxi on May 30, 2020

Given two integer arrays of equal length target and arr.

In one step, you can select any non-empty sub-array of arr and reverse it. You are allowed to make any number of steps.

Return True if you can make arr equal to target, or False otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse sub-array [2,4,1], arr becomes [1,4,2,3]
2- Reverse sub-array [4,2], arr becomes [1,2,4,3]
3- Reverse sub-array [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [1,12], arr = [12,1]
Output: true

Example 4:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr doesn't have value 9 and it can never be converted to target.

Example 5:

Input: target = [1,1,1,1,1], arr = [1,1,1,1,1]
Output: true

Constraints:

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

Solution: Counting

target and arr must have same elements.

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

C++

// Author: Huahua

class Solution {

public:

bool canBeEqual(vector<int>& target, vector<int>& arr) {

vector<int> t(1001);

vector<int> a(1001);

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

++t[target[i]];

++a[arr[i]];

}

return t == a;

}

};

Python3

# Author: Huahua

class Solution:

def canBeEqual(self, target: List[int], arr: List[int]) -> bool:

return Counter(target) == Counter(arr)

花花酱 LeetCode 1450. Number of Students Doing Homework at a Given Time

By zxi on May 16, 2020

Given two integer arrays startTime and endTime and given an integer queryTime.

The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:

Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn't doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and also wasn't doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.

Example 2:

Input: startTime = [4], endTime = [4], queryTime = 4
Output: 1
Explanation: The only student was doing their homework at the queryTime.

Example 3:

Input: startTime = [4], endTime = [4], queryTime = 5
Output: 0

Example 4:

Input: startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
Output: 0

Example 5:

Input: startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
Output: 5

Constraints:

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {

int ans = 0;

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

if (startTime[i] <= queryTime && queryTime <= endTime[i]) ++ans;

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:

return sum(s <= queryTime <= e for s, e in zip(startTime, endTime))