Posts tagged as “array”

花花酱 LeetCode 1365. How Many Numbers Are Smaller Than the Current Number

By zxi on March 2, 2020

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

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

Constraints:

2 <= nums.length <= 500
0 <= nums[i] <= 100

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

vector<int> ans(n);

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

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

if (i != j && nums[j] < nums[i]) ++ans[i];

return ans;

}

};

Solution 2: Sort + Binary Search

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

vector<int> s(nums);

sort(begin(s), end(s));

vector<int> ans(n);

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

ans[i] = distance(begin(s), lower_bound(begin(s), end(s), nums[i]));

return ans;

}

};

Solution 3: Cumulative frequency

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> f(101);

for (int x : nums) ++f[x];

partial_sum(begin(f), end(f), begin(f));

for (int& x : nums)

x = x == 0 ? 0 : f[x - 1];

return nums;

}

};

花花酱 LeetCode 1356. Sort Integers by The Number of 1 Bits

By zxi on February 22, 2020

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Example 3:

Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:

Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:

Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 10^4

Solution: Sorting

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

C++

// Author: Huahua

class Solution {

public:

vector<int> sortByBits(vector<int>& arr) {

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

int key_a = __builtin_popcount(a);

int key_b = __builtin_popcount(b);

if (key_a != key_b) return key_a < key_b;

return a < b;

});

return arr;

}

};

Python3

# Author: Huahua

class Solution:

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

return sorted(arr, key=lambda x: (bin(x).count('1') << 16) + x)

花花酱 LeetCode 1351. Count Negative Numbers in a Sorted Matrix

By zxi on February 16, 2020

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.

Return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

Solution 1: Brute Force

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

C++

// Author: Huahua, 16 ms, 10.4 MB

class Solution {

public:

int countNegatives(vector<vector<int>>& grid) {

int ans = 0;

for (const auto& row : grid)

for (const auto x : row)

ans += x < 0;

return ans;

}

};

Solution 2: Find the frontier

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

C++

// Author: Huahua, 16 ms, 10.4 MB

class Solution {

public:

int countNegatives(vector<vector<int>>& grid) {

int ans = 0;

int m = grid.size();

int n = grid[0].size();

int r = m - 1;

int c = 0;

while (r >= 0 && c < n) {

if (grid[r][c] < 0) {

ans += n - c;

--r;

} else {

++c;

}

return ans;

}

};

花花酱 LeetCode 1331. Rank Transform of an Array

By zxi on January 26, 2020

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Solution: Sorting + HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<int> arrayRankTransform(vector<int>& arr) {

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

unordered_map<int, int> m;

int r = 0;

for (const int v : s) m[v] = ++r;

vector<int> ans(arr.size());

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

ans[i] = m[arr[i]];

return ans;

}

};

花花酱 LeetCode 1330. Reverse Subarray To Maximize Array Value

By zxi on January 26, 2020

You are given an integer array nums. The value of this array is defined as the sum of |nums[i]-nums[i+1]| for all 0 <= i < nums.length-1.

You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once.

Find maximum possible value of the final array.

Example 1:

Input: nums = [2,3,1,5,4]
Output: 10
Explanation: By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.

Example 2:

Input: nums = [2,4,9,24,2,1,10]
Output: 68

Constraints:

1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5

Solution: Greedy

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

C++

// Author: Huahua

class Solution {

public:

int maxValueAfterReverse(vector<int>& nums) {

const int n = nums.size();

int sum = 0;

int gain = 0;

int hi = INT_MIN;

int lo = INT_MAX;

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

int n1 = nums[i];

int n2 = nums[i + 1];

sum += abs(n1 - n2);

gain = max({gain,

abs(nums[0] - n2) - abs(n1 - n2),

abs(nums[n - 1] - n1) - abs(n1 - n2)});

hi = max(hi, min(n1, n2));

lo = min(lo, max(n1, n2));

}

return sum + max(gain, (hi - lo) * 2);

}

};