Posts tagged as “medium”

花花酱 LeetCode 240. Search a 2D Matrix II

By zxi on March 13, 2020

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Solution 1: Two Pointers

Start from first row + last column, if the current value is larger than target, –column; if smaller then ++row.

e.g.
1. r = 0, c = 4, v = 15, 15 > 5 => –c
2. r = 0, c = 3, v = 11, 11 > 5 => –c
3. r = 0, c = 2, v = 7, 7 > 5 => –c
4. r = 0, c = 1, v = 4, 4 < 5 => ++r
5. r = 1, c = 1, v = 5, 5 = 5, found it!

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

C++

// Author: Huahua

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty() || matrix[0].empty()) return false;

const int m = matrix.size();

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

int r = 0;

int c = matrix[0].size() - 1;

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

if (matrix[r][c] == target) return true;

else if (matrix[r][c] > target) --c;

else ++r;

}

return false;

}

};

花花酱 LeetCode 229. Majority Element II

By zxi on March 13, 2020

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution: Boyer–Moore Voting Algorithm

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

C++

// Author: Huahua

class Solution {

public:

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

int n1 = 0;

int c1 = 0;

int n2 = 1;

int c2 = 0;

for (int num : nums) {

if (num == n1) {

++c1;

} else if (num == n2) {

++c2;

} else if (c1 == 0) {

n1 = num;

c1 = 1;

} else if (c2 == 0) {

n2 = num;

c2 = 1;

} else {

--c1;

--c2;

}

c1 = c2 = 0;

for (int num : nums) {

if (num == n1) ++c1;

else if (num == n2) ++c2;

}

const int c = nums.size() / 3;

vector<int> ans;

if (c1 > c) ans.push_back(n1);

if (c2 > c) ans.push_back(n2);

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def majorityElement(self, nums: List[int]) -> List[int]:

n1, c1, n2, c2 = 0, 0, 1, 0

for num in nums:

if num == n1: c1 += 1

elif num == n2: c2 += 1

elif c1 == 0: n1, c1 = num, 1

elif c2 == 0: n2, c2 = num, 1

else: c1, c2 = c1 - 1, c2 -1

c1, c2 = 0, 0

for num in nums:

if num == n1: c1 += 1

elif num == n2: c2 += 1

ans = []

if c1 > len(nums) // 3: ans.append(n1)

if c2 > len(nums) // 3: ans.append(n2)

return ans

花花酱 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

By zxi on March 13, 2020

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Solution: Recursion

Traverse both trees in the same order, if original == target, return cloned.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {

if (!original) return nullptr;

if (original == target) return cloned;

auto l = getTargetCopy(original->left, cloned->left, target);

auto r = getTargetCopy(original->right, cloned->right, target);

return l ? l : r;

}

};

Python3

# Author: Huahua

class Solution:

def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

if not original: return None

if original == target: return cloned

return self.getTargetCopy(original.left, cloned.left, target) or \

self.getTargetCopy(original.right, cloned.right, target)

花花酱 LeetCode 375. Guess Number Higher or Lower II

By zxi on March 13, 2020

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution: DP

Use dp[l][r] to denote the min money to win the game if the current guessing range is [l, r], to guarantee a win, we need to try all possible numbers in [l, r]. Let say we guess K, we need to pay K and the game might continue if we were wrong. cost will be K + max(dp(l, K-1), dp(K+1, r)), we need max to cover all possible cases. Among all Ks, we picked the cheapest one.

dp[l][r] = min(k + max(dp[l][k – 1], dp[k+1][r]), for l <= k <= r.

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

C++

// Author: Huahua

class Solution {

public:

int getMoneyAmount(int n) {

constexpr int kInf = 1e9;

vector<vector<int>> cache(n + 2, vector<int>(n + 2, kInf));

function<int(int, int)> dp = [&](int l, int r) {

int& ans = cache[l][r];

if (l >= r) return 0;

if (ans != kInf) return ans;

for (int x = l; x <= r; ++x)

ans = min(ans, x + max(dp(l, x - 1), dp(x + 1, r)));

return ans;

};

return dp(1, n);

}

};

Python3

# Author: Huahua

class Solution:

def getMoneyAmount(self, n: int) -> int:

@lru_cache(maxsize=None)

def dp(l, r):

return min([k + max(dp(l, k - 1), dp(k + 1, r))

for k in range(l, r + 1)]) if l < r else 0

return dp(1, n)

花花酱 LeetCode 355. Design Twitter

By zxi on March 10, 2020

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

Solution: hashtables

Time complexity:
postTweet O(1)
follow O(1)
unfollow O(1)
getNewsFeed O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

constexpr size_t kMaxTweets = 10;

class Twitter {

public:

/** Initialize your data structure here. */

Twitter() {}

/** Compose a new tweet. */

void postTweet(int userId, int tweetId) {

auto& tweets = user_tweets_[userId];

if (tweets.size() == kMaxTweets)

tweets.pop_front();

tweets.emplace_back(++time_, tweetId);

}

/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */

vector<int> getNewsFeed(int userId) {

vector<pair<int, int>> feed(begin(user_tweets_[userId]),

end(user_tweets_[userId]));

for (int uid : user_followers_[userId])

feed.insert(end(feed),

begin(user_tweets_[uid]),

end(user_tweets_[uid]));

sort(rbegin(feed), rend(feed));

vector<int> ans;

for (int i = 0; i < min(kMaxTweets, feed.size()); ++i)

ans.push_back(feed[i].second);

return ans;

}

/** Follower follows a followee. If the operation is invalid, it should be a no-op. */

void follow(int followerId, int followeeId) {

if (followerId == followeeId) return;

user_followers_[followerId].insert(followeeId);

}

/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */

void unfollow(int followerId, int followeeId) {

if (followerId == followeeId) return;

user_followers_[followerId].erase(followeeId);

}

private:

int time_;

unordered_map<int, deque<pair<int, int>>> user_tweets_;

unordered_map<int, set<int>> user_followers_;

};

/**

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

* Twitter* obj = new Twitter();

* obj->postTweet(userId,tweetId);

* vector<int> param_2 = obj->getNewsFeed(userId);

* obj->follow(followerId,followeeId);

* obj->unfollow(followerId,followeeId);

Posts tagged as “medium”

花花酱 LeetCode 240. Search a 2D Matrix II

Solution 1: Two Pointers

C++

花花酱 LeetCode 229. Majority Element II

Solution: Boyer–Moore Voting Algorithm

C++

Python3

Related Problem

花花酱 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Solution: Recursion

C++

Python3

花花酱 LeetCode 375. Guess Number Higher or Lower II

Solution: DP

C++

Python3

花花酱 LeetCode 355. Design Twitter

Solution: hashtables

C++