Posts tagged as “array”

花花酱 LeetCode 1535. Find the Winner of an Array Game

By zxi on August 1, 2020

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

Constraints:

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr contains distinct integers.
1 <= k <= 10^9

Solution 1: Simulation with a List

Observation : if k >= n – 1, ans = max(arr)

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

C++

class Solution {

public:

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

if (k >= arr.size()) return *max_element(begin(arr), end(arr));

int win = 0;

list<int> a(begin(arr), end(arr));

while (true) {

auto it0 = begin(a);

auto it1 = next(it0);

if (*it0 > *it1) {

a.splice(a.end(), a, it1);

++win;

} else {

swap(it0, it1);

a.splice(a.end(), a, it1);

win = 1;

}

if (win == k) return *it0;

}

return -1;

}

};

Solution 2: One pass

Since smaller numbers will be put to the end of the array, we must compare the rest of array before meeting those used numbers again. And the winner is monotonically increasing. So we can do it in one pass, just keep the largest number seen so far. If we reach to the end of the array, arr[0] will be max(arr) and it will always win no matter what k is.

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

C++

class Solution {

public:

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

int winner = arr[0];

int win = 0;

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

if (arr[i] > winner) {

winner = arr[i];

win = 0;

}

if (++win == k) break;

}

return winner;

}

};

Java

class Solution {

public int getWinner(int[] arr, int k) {

int winner = arr[0];

int win = 0;

for (int i = 1; i < arr.length && win < k; ++i, ++win)

if (arr[i] > winner) {

winner = arr[i];

win = 0;

}

return winner;

}

Python3

class Solution:

def getWinner(self, arr: List[int], k: int) -> int:

winner = arr[0]

win = 0

for x in arr[1:]:

if x > winner:

winner, win = x, 0

win += 1

if win == k: break

return winner

花花酱 LeetCode 1534. Count Good Triplets

By zxi on August 1, 2020

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.

Constraints:

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countGoodTriplets(vector<int>& arr, int a, int b, int c) {

const int n = arr.size();

int ans = 0;

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

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

for (int k = j + 1; k < n; ++k)

if (abs(arr[i] - arr[j]) <= a &&

abs(arr[j] - arr[k]) <= b &&

abs(arr[i] - arr[k]) <= c)

++ans;

return ans;

}

};

花花酱 LeetCode 1502. Can Make Arithmetic Progression From Sequence

By zxi on July 5, 2020

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

Solution 1: Sort and check.

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

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

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

const int diff = arr[1] - arr[0];

for (int i = 2; i < arr.size(); ++i)

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

return true;

}

};

Java

// Author: Huahua

class Solution {

public boolean canMakeArithmeticProgression(int[] arr) {

Arrays.sort(arr);

int diff = arr[1] - arr[0];

for (int i = 2; i < arr.length; ++i)

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

return true;

}

python3

class Solution:

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

arr.sort()

diff = arr[1] - arr[0]

return all(i - j == diff for i, j in zip(arr[1:], arr[:-1]))

Solution 2: Rearrange the array

Find min / max / diff and put each element into its correct position by swapping elements in place.

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

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

const int n = arr.size();

const auto [loit, hiit] = minmax_element(cbegin(arr), cend(arr));

const auto [lo, hi] = pair{*loit, *hiit};

if ((hi - lo) % (n - 1)) return false;

const int diff = (hi - lo) / (n - 1);

if (diff == 0) return true;

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

if ((arr[i] - lo) % diff) return false;

const int idx = (arr[i] - lo) / diff;

if (idx != i) swap(arr[i--], arr[idx]);

}

return true;

}

};

花花酱 LeetCode 1493. Longest Subarray of 1’s After Deleting One Element

By zxi on June 27, 2020

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array.

Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Example 4:

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

Example 5:

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

Constraints:

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.

Solution 1: DP

Preprocess:
l[i] := longest 1s from left side ends with nums[i], l[i] = nums[i] + nums[i] * l[i – 1]
r[i] := longest 1s from right side ends with nums[i], r[i] = nums[i] + nums[i] * r[i + 1]

Use each node as a bridge (ignored), the total number of consecutive 1s = l[i – 1] + r[i + 1].

ans = max{l[i-1] + r[i +1]}
Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

vector<int> l(n);

vector<int> r(n);

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

l[i] = (i > 0 ? l[i - 1] * nums[i] : 0) + nums[i];

for (int i = n - 1; i >= 0; --i)

r[i] = (i < n - 1 ? r[i + 1] * nums[i] : 0) + nums[i];

int ans = 0;

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

ans = max(ans, (i > 0 ? l[i - 1] : 0) +

(i < n - 1 ? r[i + 1] : 0));

return ans;

}

};

Solution 2: DP

dp[i][0] := longest subarray ends with nums[i] has no ones.
dp[i][0] := longest subarray ends with nums[i] has 1 one.
if nums[i] == 1:
dp[i][0] = dp[i – 1][0] + 1
dp[i][1] = dp[i – 1][1] + 1
if nums[i] == 0:
dp[i][0] = 0
dp[i][1] = dp[i – 1][0] + 1
Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

// dp[i][0] := longest subarray ends with nums[i-1] has no zeros.

// dp[i][0] := longest subarray ends with nums[i-1] has 1 zero.

vector<vector<int>> dp(n + 1, vector<int>(2));

int ans = 0;

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

if (nums[i - 1] == 1) {

dp[i][0] = dp[i - 1][0] + 1;

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

} else {

dp[i][0] = 0;

dp[i][1] = dp[i - 1][0] + 1;

}

ans = max({ans, dp[i][0] - 1, dp[i][1] - 1});

}

return ans;

}

};

Solution 3: Sliding Window

Maintain a sliding window l ~ r s.t sum(num[l~r]) >= r – l. There can be at most one 0 in the window.
ans = max{r – l} for all valid windows.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

int sum = 0; // sum of nums[l~r].

for (int l = 0, r = 0; r < n; ++r) {

sum += nums[r];

// Maintain sum >= r - l, at most 1 zero.

while (l < r && sum < r - l)

sum -= nums[l++];

ans = max(ans, r - l);

}

return ans;

}

};

花花酱 LeetCode 1491. Average Salary Excluding the Minimum and Maximum Salary

By zxi on June 27, 2020

Given an array of unique integers salary where salary[i] is the salary of the employee i.

Return the average salary of employees excluding the minimum and maximum salary.

Example 1:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500

Example 2:

Input: salary = [1000,2000,3000]
Output: 2000.00000
Explanation: Minimum salary and maximum salary are 1000 and 3000 respectively.
Average salary excluding minimum and maximum salary is (2000)/1= 2000

Example 3:

Input: salary = [6000,5000,4000,3000,2000,1000]
Output: 3500.00000

Example 4:

Input: salary = [8000,9000,2000,3000,6000,1000]
Output: 4750.00000

Constraints:

3 <= salary.length <= 100
10^3 <= salary[i] <= 10^6
salary[i] is unique.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

double average(vector<int>& salary) {

auto [lit, hit] = minmax_element(begin(salary), end(salary));

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

return (sum - *lit - *hit) * 1.0 / (salary.size() - 2);

}

};