Posts published in “Algorithms”

花花酱 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 1348. Tweet Counts Per Frequency

By zxi on February 29, 2020

Implement the class TweetCounts that supports two methods:

1. recordTweet(string tweetName, int time)

Stores the tweetName at the recorded time (in seconds).

2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

Returns the total number of occurrences for the given tweetName per minute, hour, or day (depending on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
The first time interval always starts from the startTime, so the time intervals are [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)> for some non-negative number i and delta (which depends on freq).

Example:

Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

Output
[null,null,null,null,[2]
[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet.
tweetCounts.recordTweet("tweet3", 120);                            // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120.
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.

Constraints:

There will be at most 10000 operations considering both recordTweet and getTweetCountsPerFrequency.
0 <= time, startTime, endTime <= 10^9

Solution: Hashtable + binary search

Time complexity:
Record: O(logn)
getCount: O(logn + |entries|)

Space complexity: O(n)

C++

// Author: Huahua

class TweetCounts {

public:

TweetCounts() {

m_.clear();

}

void recordTweet(string tweetName, int time) {

m_[tweetName].insert(time);

}

vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {

auto tit = m_.find(tweetName);

if (tit == m_.end()) return {};

const set<int>& s = tit->second;

int delta = 1;

if (freq == "minute") delta = 60;

else if (freq == "hour") delta = 60 * 60;

else if (freq == "day") delta = 60 * 60 * 24;

int slots = (endTime - startTime + delta - 1) / delta;

vector<int> ans(slots);

for (int i = startTime; i <= endTime; i += delta) {

auto it1 = s.lower_bound(i);

auto it2 = s.lower_bound(min(i + delta, endTime + 1));

ans.push_back(distance(it1, it2)); // O(|entries|)

}

return ans;

}

private:

unordered_map<string, set<int>> m_;

};

花花酱 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 1352. Product of the Last K Numbers

By zxi on February 16, 2020

Implement the class ProductOfNumbers that supports two methods:

1. add(int num)

Adds the number num to the back of the current list of numbers.

2. getProduct(int k)

Returns the product of the last k numbers in the current list.
You can assume that always the current list has at least k numbers.

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:

Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output: [null,null,null,null,null,null,20,40,0,null,32]
Explanation:
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3] 
productOfNumbers.add(0);        // [3,0] 
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20.
The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40 
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32

Constraints:

There will be at most 40000 operations considering both add and getProduct.
0 <= num <= 100
1 <= k <= 40000

Solution: Prefix product

Use p[i] to store the prod of a1*a2*…ai
p[i] = ai*p[i-1]
If ai is 0, reset p = [1].
Compare k with the len(p), if k is greater than len(p) which means there is 0 recently, return 0.
otherwise return p[n] / p[n – k – 1]

Time complexity: Add: O(1), getProduct: O(1)
Space complexity: O(n)

C++

// Author: Huahua

class ProductOfNumbers {

public:

ProductOfNumbers(): p_(1, 1) { }

void add(int num) {

if (num == 0) {

p_.clear();

p_.push_back(1);

} else {

p_.push_back(p_.back() * num);

}

int getProduct(int k) {

if (k >= p_.size()) return 0;

// a_1*a_2*...*a_n / a_1*a_2*...*a_n-k-1.

return p_.back() / p_[p_.size() - k - 1];

}

private:

vector<int> p_;

};

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

}

};