Posts tagged as “array”

花花酱 LeetCode 1566. Detect Pattern of Length M Repeated K or More Times

By zxi on August 29, 2020

Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.

A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

Constraints:

2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100

Solution 1: Brute Force

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

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

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

bool valid = true;

for (int j = 1; j < k && valid; ++j)

for (int p = 0; p < m && valid; ++p)

if (arr[i + j * m + p] != arr[i + p])

valid = false;

if (valid) return true;

}

return false;

}

};

Solution 2: Shift and count

Since we need k consecutive subarrays, we can compare arr[i] with arr[i + m], if they are the same, increase the counter, otherwise reset the counter. If the counter reaches (k – 1) * m, it means we found k consecutive subarrays of length m.

ex1: arr = [1,2,4,4,4,4], m = 1, k = 3
i arr[i], arr[i + m] counter
0 1. 2. 0
0 2. 4. 0
0 4. 4. 1
0 4. 4. 2. <– found

ex2: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
i arr[i], arr[i + m] counter
0 1. 1. 1
0 2. 2. 2 <– found

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

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

int count = 0;

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

if (arr[i] == arr[i + m]) {

if (++count == (k - 1) * m) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1539. Kth Missing Positive Number

By zxi on August 9, 2020

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the k^th positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5^th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2^nd missing positive integer is 6.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution 1: HashTable

Store all the elements into a hashtable, and check from 1 to max(arr).

Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

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

unordered_set<int> s(begin(arr), end(arr));

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

if (!s.count(i)) --k;

if (k == 0) return i;

}

return arr.back() + k;

}

};

Solution 2: Binary Search

We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.

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

C++

// Author: Huahua

class Solution {

public:

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

int l = 0;

int r = arr.size();

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

};

Java

class Solution {

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

int l = 0;

int r = arr.length;

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

Python3

class Solution:

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

l, r = 0, len(arr)

while l < r:

m = l + (r - l) // 2

if arr[m] - (m + 1) >= k:

r = m

else:

l = m + 1

return l + k

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

}

};