Posts published in “Array”

花花酱 LeetCode 1442. Count Triplets That Can Form Two Arrays of Equal XOR

By zxi on May 11, 2020

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let’s define a and b as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:

Input: arr = [1,1,1,1,1]
Output: 10

Example 3:

Input: arr = [2,3]
Output: 0

Example 4:

Input: arr = [1,3,5,7,9]
Output: 3

Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

Constraints:

1 <= arr.length <= 300
1 <= arr[i] <= 10^8

Solution 1: Brute Force (TLE)

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

C++

// Author: Huahua

class Solution {

public:

int countTriplets(vector<int>& arr) {

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; k < n; ++k) {

int a = 0;

int b = 0;

for (int t = i; t < j; ++t)

a ^= arr[t];

for (int t = j; t <= k; ++t)

b ^= arr[t];

if (a == b) ++ans;

}

return ans;

}

};

Solution 2: Prefix XORs

Let xors[i] = arr[0] ^ arr[1] ^ … ^ arr[i-1]
arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1] = (arr[0] ^ … ^ arr[j – 1]) ^ (arr[0] ^ … ^ arr[i-1]) = xors[j] ^ xors[i]

We then can compute a and b in O(1) time.

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

C++

// Author: Huahua, 232 ms

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

vector<int> xors(n + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

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

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

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

const int a = xors[j] ^ xors[i];

const int b = xors[k + 1] ^ xors[j];

if (a == b) ++ans;

}

return ans;

}

};

Solution 3: Prefix XORs II

a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
a == b => a ^ b == 0
XORs(i ~ k) == 0
XORS(0 ~ k) ^ XORs(0 ~ i – 1) = 0

Problem => find all pairs of (i – 1, k) such that xors[k+1] == xors[i]
For each pair (i – 1, k), there are k – i positions we can insert j.

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

C++

// Author: Huahua

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

vector<int> xors(n + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

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

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

if (xors[k + 1] == xors[i])

ans += k - i;

return ans;

}

};

Solution 3: HashTable

Similar to target sum, use a hashtable to store the frequency of each prefix xors.

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

C++

// Author: Huahua

// Author: Huahua 4 ms

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

unordered_map<int, int> freq{{0, 1}};

unordered_map<int, int> sum;

int X = 0;

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

X ^= arr[i];

ans += freq[X] * i - sum[X];

++freq[X];

sum[X] += i + 1;

}

return ans;

}

};

花花酱 LeetCode 1437. Check If All 1’s Are at Least Length K Places Away

By zxi on May 3, 2020

Given an array nums of 0s and 1s and an integer k, return True if all 1’s are at least k places away from each other, otherwise return False.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true

Example 4:

Input: nums = [0,1,0,1], k = 1
Output: true

Constraints:

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

Solution: Scan the array

Only need to check adjacent ones. This problem should be easy instead of medium.

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

C++

// Author: Huahua

class Solution {

public:

bool kLengthApart(vector<int>& nums, int k) {

int d = k + 1; // distant enough

for (int n : nums) {

if (n == 0) {

++d;

} else {

if (d < k) return false;

d = 0;

}

return true;

}

};

花花酱 LeetCode 1431. Kids With the Greatest Number of Candies

By zxi on May 3, 2020

Given the array candies and the integer extraCandies, where candies[i] represents the number of candies that the ith kid has.

For each kid check if there is a way to distribute extraCandies among the kids such that he or she can have the greatest number of candies among them. Notice that multiple kids can have the greatest number of candies.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: 
Kid 1 has 2 candies and if he or she receives all extra candies (3) will have 5 candies --- the greatest number of candies among the kids. 
Kid 2 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids. 
Kid 3 has 5 candies and this is already the greatest number of candies among the kids. 
Kid 4 has 1 candy and even if he or she receives all extra candies will only have 4 candies. 
Kid 5 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids.

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false] 
Explanation: There is only 1 extra candy, therefore only kid 1 will have the greatest number of candies among the kids regardless of who takes the extra candy.

Example 3:

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Constraints:

2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

Solution: Finding max

Find the maximum candies that a kid has.

ans[i] = (candies[i] + extra) >= max_candies

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {

const int threshold = *max_element(begin(candies), end(candies));

vector<bool> ans(candies.size());

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

ans[i] = (candies[i] + extraCandies) >= threshold;

return ans;

}

};

Python

# Author: Huahua

class Solution:

def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:

m = max(candies)

return [c + extraCandies >= m for c in candies]

花花酱 LeetCode 1423. Maximum Points You Can Obtain from Cards

By zxi on April 25, 2020

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

Solution: Sliding Window

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(vector<int>& p, int k) {

const int n = p.size();

int cur = accumulate(begin(p), begin(p) + k, 0);

int ans = cur;

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

cur = cur - p[k - i - 1] + p[n - i - 1];

ans = max(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 1413. Minimum Value to Get Positive Step by Step Sum

By zxi on April 18, 2020

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Example 1:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
                step by step sum
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

Example 2:

Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.

Example 3:

Input: nums = [1,-2,-3]
Output: 5

Constraints:

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

Solution: Prefix sum

Find the minimum prefix sum, ans = – min(prefix_sum, 0) + 1

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

C++

// Author: Huahua

class Solution {

public:

int minStartValue(vector<int>& nums) {

int min_sum = 0;

int sum = 0;

for (int num : nums) {

sum += num;

min_sum = min(min_sum, sum);

}

return -min_sum + 1;

}

};