Posts tagged as “medium”

花花酱 LeetCode 2080. Range Frequency Queries

By zxi on November 21, 2021

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

Input
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output

[null, 1, 2]

Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
At most 10⁵ calls will be made to query

Solution: Hashtable + Binary Search

Time complexity: Init: O(max(arr) + n), query: O(logn)
Space complexity: O(max(arr) + n)

C++

// Author: Huahua

class RangeFreqQuery {

public:

RangeFreqQuery(vector<int>& arr) : s_(10001) {

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

s_[arr[i]].push_back(i);

}

int query(int left, int right, int value) {

const auto& m = s_[value];

if (m.empty()) return 0;

auto r = prev(upper_bound(begin(m), end(m), right));

auto l = lower_bound(begin(m), end(m), left);

return r - l + 1;

}

private:

vector<vector<int>> s_;

};

/**

* Your RangeFreqQuery object will be instantiated and called as such:

* RangeFreqQuery* obj = new RangeFreqQuery(arr);

* int param_1 = obj->query(left,right,value);

花花酱 LeetCode 2079. Watering Plants

By zxi on November 20, 2021

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i^th plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

Water the plants in order from left to right.
After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i^th plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

Input: plants = [2,2,3,3], capacity = 5
Output: 14
Explanation: Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

Input: plants = [1,1,1,4,2,3], capacity = 4
Output: 30
Explanation: Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

Input: plants = [7,7,7,7,7,7,7], capacity = 8
Output: 49
Explanation: You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

n == plants.length
1 <= n <= 1000
1 <= plants[i] <= 10⁶
max(plants[i]) <= capacity <= 10⁹

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int wateringPlants(vector<int>& plants, int capacity) {

const int n = plants.size();

int ans = 0;

for (int i = 0, c = capacity; i < n; c -= plants[i++], ++ans) {

if (c >= plants[i]) continue;

ans += i * 2;

c = capacity;

}

return ans;

}

};

花花酱 LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences

By zxi on November 20, 2021

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.

Return the maximum possible product of the lengths of the two palindromic subsequences.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.

Example 1:

Input: s = "leetcodecom"
Output: 9
Explanation: An optimal solution is to choose "ete" for the 1^st subsequence and "cdc" for the 2^nd subsequence.
The product of their lengths is: 3 * 3 = 9.

Example 2:

Input: s = "bb"
Output: 1
Explanation: An optimal solution is to choose "b" (the first character) for the 1^st subsequence and "b" (the second character) for the 2^nd subsequence.
The product of their lengths is: 1 * 1 = 1.

Example 3:

Input: s = "accbcaxxcxx"
Output: 25
Explanation: An optimal solution is to choose "accca" for the 1^st subsequence and "xxcxx" for the 2^nd subsequence.
The product of their lengths is: 5 * 5 = 25.

Constraints:

2 <= s.length <= 12
s consists of lowercase English letters only.

Solution 1: DFS

Time complexity: O(3ⁿ*n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(string s) {

auto isPalindrom = [](const string& s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != s[s.size() - i - 1]) return false;

return true;

};

const int n = s.size();

vector<string> ss(3);

size_t ans = 0;

function<void(int)> dfs = [&](int i) -> void {

if (i == n) {

if (isPalindrom(ss[0]) && isPalindrom(ss[1]))

ans = max(ans, ss[0].size() * ss[1].size());

return;

}

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

ss[k].push_back(s[i]);

dfs(i + 1);

ss[k].pop_back();

}

};

dfs(0);

return ans;

}

};

Solution: Subsets + Bitmask + All Pairs

Time complexity: O(2²ⁿ)
Space complexity: O(2ⁿ)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(string s) {

auto isPalindrom = [](const string& s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != s[s.size() - i - 1]) return false;

return true;

};

const int n = s.size();

unordered_set<int> p;

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

string t;

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

if (i >> j & 1) t.push_back(s[j]);

if (isPalindrom(t))

p.insert(i);

}

int ans = 0;

for (int s1 : p)

for (int s2 : p)

if (!(s1 & s2))

ans = max(ans, __builtin_popcount(s1) * __builtin_popcount(s2));

return ans;

}

};

花花酱 LeetCode 2001. Number of Pairs of Interchangeable Rectangles

By zxi on November 20, 2021

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [width_i, height_i] denotes the width and height of the i^th rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if width_i/height_i == width_j/height_j (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.

Constraints:

n == rectangles.length
1 <= n <= 10⁵
rectangles[i].length == 2
1 <= width_i, height_i <= 10⁵

Solution: Hashtable

Use aspect ratio as the key.

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

C++

// Author: Huahua

class Solution {

public:

long long interchangeableRectangles(vector<vector<int>>& rectangles) {

long long ans = 0;

unordered_map<long long, int> m;

for (const auto& r : rectangles) {

long long d = gcd(r[0], r[1]);

ans += m[((r[0] / d) << 20) | (r[1] / d)]++;

}

return ans;

}

};

花花酱 LeetCode 2075. Decode the Slanted Ciphertext

By zxi on November 15, 2021

A string originalText is encoded using a slanted transposition cipher to a string encodedText with the help of a matrix having a fixed number of rows rows.

originalText is placed first in a top-left to bottom-right manner.

The blue cells are filled first, followed by the red cells, then the yellow cells, and so on, until we reach the end of originalText. The arrow indicates the order in which the cells are filled. All empty cells are filled with ' '. The number of columns is chosen such that the rightmost column will not be empty after filling in originalText.

encodedText is then formed by appending all characters of the matrix in a row-wise fashion.

The characters in the blue cells are appended first to encodedText, then the red cells, and so on, and finally the yellow cells. The arrow indicates the order in which the cells are accessed.

For example, if originalText = "cipher" and rows = 3, then we encode it in the following manner:

The blue arrows depict how originalText is placed in the matrix, and the red arrows denote the order in which encodedText is formed. In the above example, encodedText = "ch ie pr".

Given the encoded string encodedText and number of rows rows, return the original string originalText.

Note: originalText does not have any trailing spaces ' '. The test cases are generated such that there is only one possible originalText.

Example 1:

Input: encodedText = "ch   ie   pr", rows = 3
Output: "cipher"
Explanation: This is the same example described in the problem description.

Example 2:

Input: encodedText = "iveo    eed   l te   olc", rows = 4
Output: "i love leetcode"
Explanation: The figure above denotes the matrix that was used to encode originalText. 
The blue arrows show how we can find originalText from encodedText.

Example 3:

Input: encodedText = "coding", rows = 1
Output: "coding"
Explanation: Since there is only 1 row, both originalText and encodedText are the same.

Example 4:

Input: encodedText = " b  ac", rows = 2
Output: " abc"
Explanation: originalText cannot have trailing spaces, but it may be preceded by one or more spaces.

Constraints:

0 <= encodedText.length <= 10⁶
encodedText consists of lowercase English letters and ' ' only.
encodedText is a valid encoding of some originalText that does not have trailing spaces.
1 <= rows <= 1000
The testcases are generated such that there is only one possible originalText.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string decodeCiphertext(string encodedText, int rows) {

const int cols = encodedText.size() / rows;

string ans;

ans.reserve(encodedText.size());

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

for (int j = 0; j < rows && i + j < cols; ++j)

ans += encodedText[j * cols + j + i];

while (ans.size() && !isalpha(ans.back())) ans.pop_back();

return ans;

}

};