Posts tagged as “array”

花花酱 LeetCode 2451. Odd String Difference

By zxi on October 31, 2022

You are given an array of equal-length strings words. Assume that the length of each string is n.

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] - words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0, 'b' is 1, and 'z' is 25.

For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string in words that has different difference integer array.

Example 1:

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation: 
- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
- The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
- The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. 
The odd array out is [1, 1], so we return the corresponding string, "abc".

Example 2:

Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].

Constraints:

3 <= words.length <= 100
n == words[i].length
2 <= n <= 20
words[i] consists of lowercase English letters.

Solution: Comparing with first string.

Let us pick words[0] as a reference for comparison, assuming it’s valid. If we only found one instance say words[i], that is different than words[0], we know that words[i] is bad, otherwise we should see m – 1 different words which means words[0] itself is bad.

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

C++

// Author: Huahua

class Solution {

public:

string oddString(vector<string>& words) {

const int m = words.size();

const int n = words[0].size();

int count = 0;

int bad = 0;

for (int i = 1; i < m; ++i)

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

if (words[i][j] - words[i][j - 1]

!= words[0][j] - words[0][j - 1]) {

++count;

bad = i;

break;

}

return words[count == 1 ? bad : 0];

}

};

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

By zxi on October 15, 2022

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints:

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
nums[i] != 0

Solution 1: Hashtable

We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

unordered_set<int> s;

int ans = -1;

for (int x : nums) {

if (abs(x) > ans && s.count(-x))

ans = abs(x);

s.insert(x);

}

return ans;

}

};

Solution 2: Sorting

Sort the array by abs(x) in descending order.

[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]

Check whether arr[i] = -arr[i-1].

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

sort(begin(nums), end(nums), [](int a, int b){

return abs(a) == abs(b) ? a < b : abs(a) > abs(b);

});

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

if (nums[i] == -nums[i - 1]) return nums[i];

return -1;

}

};

Solution 3: Two Pointers

Sort the array.

Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum < 0, ++i else –j.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

sort(begin(nums), end(nums));

int ans = -1;

for (int i = 0, j = nums.size() - 1; i < j; ) {

const int s = nums[i] + nums[j];

if (s == 0) {

ans = max(ans, nums[j]);

++i, --j;

} else if (s < 0) {

++i;

} else {

--j;

}

return ans;

}

};

花花酱 LeetCode 2419. Longest Subarray With Maximum Bitwise AND

By zxi on September 26, 2022

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Solution: Find the largest number

a & b <= a
a & b <= b
if b > a, a & b < b, we choose to start a new sequence of “b” instead of continuing with “ab”

Basically, we find the largest number in the array and count the longest sequence of it. Note, there will be some tricky cases like.
b b b b a b
b a b b b b
We need to return 4 instead of 1.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

int ans = 0;

int best = 0;

for (int i = 0, l = 0; i < nums.size(); ++i) {

if (nums[i] > best) {

best = nums[i];

ans = l = 1;

} else if (nums[i] == best) {

ans = max(ans, ++l);

} else {

l = 0;

}

return ans;

}

};

花花酱 LeetCode 2418. Sort the People

By zxi on September 26, 2022

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the i^th person.

Return names sorted in descending order by the people’s heights.

Example 1:

Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.

Example 2:

Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]
Explanation: The first Bob is the tallest, followed by Alice and the second Bob.

Constraints:

n == names.length == heights.length
1 <= n <= 10³
1 <= names[i].length <= 20
1 <= heights[i] <= 10⁵
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Solution: Zip and sort

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

C++

// Author: Huahua

class Solution {

public:

vector<string> sortPeople(vector<string>& names, vector<int>& heights) {

vector<pair<int, string*>> data;

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

data.emplace_back(heights[i], &names[i]);

sort(rbegin(data), rend(data));

vector<string> ans(names.size());

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

ans[i].swap(*data[i].second);

return ans;

}

};

花花酱 LeetCode 2395. Find Subarrays With Equal Sum

By zxi on September 7, 2022

Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.

Return true if these subarrays exist, and false otherwise.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.

Example 2:

Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of size 2 have the same sum.

Example 3:

Input: nums = [0,0,0]
Output: true
Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. 
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.

Constraints:

2 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

Solution: Hashset

Use a hashset to track all the sums seen so far.

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

C++

// Author: Huahua

class Solution {

public:

bool findSubarrays(vector<int>& nums) {

unordered_set<int> s;

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

if (!s.emplace(nums[i] + nums[i - 1]).second) return true;

return false;

}

};