weekly-contest-213
1번과 2번을 푸는데,
고수는 5분/5분
중수는 10분/10분
정도 걸린듯함.
leetcode.com/problems/check-array-formation-through-concatenation/
Check Array Formation Through Concatenation - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Approach 1: One by One
코드가 예쁜편
class Solution {
public boolean canFormArray(int[] arr, int[][] pieces) {
int n = arr.length;
int i = 0;
while(i < n) {
int found = -1;
for(int j = 0; j < pieces.length; j++) {
if(pieces[j][0] == arr[i]) {
found = j;
break;
}
}
if(found == -1) {
return false;
}
int[] targetPiece = pieces[found];
for(int x : targetPiece) {
if(i >= n || x != arr[i]) {
return false;
}
i++;
}
}
return true;
}
}
Complexity Analysis
Let N be the length of arr. In the worst case, the size of pieces is \mathcal{O}(N).
-
Time Complexity: \mathcal{O}(N^2). The time to find the next piece is \mathcal{O}(N), and we need to find \mathcal{O}(N) pieces at most.
-
Space Complexity: \mathcal{O}(1), since no additional data structure is allocated
Approach 2: Binary Search
Complexity Analysis
Let N be the length of arr. In the worst case, the size of pieces is \mathcal{O}(N).
-
Time Complexity: \mathcal{O}(N\log(N)). The time to find next piece using Binary Search is \mathcal{O}(\log(N)), and we need to find \mathcal{O}(N) pieces at most.
-
Space Complexity: \mathcal{O}(1), since no additional data structure is allocated.
Approach 3: HashMap
Complexity Analysis
Let N be the length of arr. In the worst case, the size of pieces is \mathcal{O}(N).
-
Time Complexity: \mathcal{O}(N). The time to find next piece is \mathcal{O}(1), and we need to find \mathcal{O}(N) pieces at most.
-
Space Complexity: \mathcal{O}(N), since we store a hashmap with \mathcal{O}(N) elements at most.
class Solution {
public boolean canFormArray(int[] arr, int[][] pieces) {
int n = arr.length; // Let N be the length of arr. In the worst case, the size of pieces is O(N)
// Space complexity is O(N), since we store a hashmap with O(N) elements at most.
Map<Integer, int[]> mapping = new HashMap<>();
for(int[] p : pieces) {
mapping.put(p[0], p);
}
// O(N). The time to find next piece is O(1), and we need to find O(N) pieces at most.
int i = 0;
while(i < n) {
if(!mapping.containsKey(arr[i])) {
return false;
}
int[] targetPiece = mapping.get(arr[i]);
for(int x : targetPiece) {
if(i >= n || x != arr[i]) {
return false;
}
i++;
}
}
return true;
}
}
leetcode.com/problems/count-sorted-vowel-strings/
Count Sorted Vowel Strings - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Approach 1: Brute Force Using Backtracking
Complexity Analysis
- Time Complexity : \mathcal{O}(n^{4}). At every level i, there are roughly i^{4} enumerations. The following figure illustrates the number of possible paths at level 2.
Since the maximum depth of recursion would be n, the time complexity to explore all the path would be roughly equal to \mathcal{O}(n^{4}).
- Space Complexity: \mathcal{O}(n). This space will be used to store the recursion stack. We can’t have more than n recursive calls on the call stack at any time.
class Solution {
public int countVowelStrings(int n) {
return countVowelStringUtil(n, 5);
}
int countVowelStringUtil(int n, int vowels) {
if(n==1) return vowels;
if(vowels == 1)
return 1;
return countVowelStringUtil(n-1, vowels) + countVowelStringUtil(n, vowels-1);
}
}
Approach 2: Decoding the Pattern, Using Recursion
class Solution {
public int countVowelStrings(int n) {
return countVowelStringUtil(n, 1);
}
int countVowelStringUtil(int n, int vowels) {
if(n==0) return 1;
int result = 0;
for(int i = vowels; i <= 5; i++) {
result += countVowelStringUtil(n-1, i);
}
return result;
}
}
Complexity Analysis
-
Time Complexity : \mathcal{O}(n^{4}), as for a given n and 5 vowels (a, e, i, o, u), there are roughly n^{4} possible candidates (Refer time complexity of Approach 1).This gives us time complexity as \mathcal{O}(n^{4}).
-
Space Complexity: \mathcal{O}(n). This space will be used to store the recursion stack. As the maximum depth of recursion would be \max(n,5), the space required for internal call stack would roughly \mathcal{O}(n).
Approach 3: Using Recursion + Memoization, Top Down Dynamic Programming
class Solution {
public int countVowelStrings(int n) {
int memo[][] = new int[n+1][6];
return countVowelStringUtil(n, 5, memo);
}
int countVowelStringUtil(int n, int vowels, int memo[][]) {
if(n==1) return vowels;
if(vowels == 1) return 1;
if (memo[n][vowels] != 0)
return memo[n][vowels];
int res = countVowelStringUtil(n - 1, vowels, memo) +
countVowelStringUtil(n, vowels - 1, memo);
memo[n][vowels] = res;
return res;
}
}
-
Time Complexity : , as for every n and we calculate result only once, the total number of nodes in the recursion tree would be n * , which is roughly equal to n.
-
Space Complexity : , as we use a 2D array of size n * and the size of internal call stack would also be n (As explained in Approach 2), the space complexity would be O(n+n) = .
Approach 4: Bottom Up Dynamic Programming, Tabulation
class Solution {
public int countVowelStrings(int n) {
int[][] dp = new int[n+1][6];
for(int vowels = 1; vowels <= 5; vowels++)
dp[1][vowels] = vowels;
for(int nValue = 2; nValue <= n; nValue++) {
dp[nValue][1] = 1;
for(int vowels = 2; vowels <= 5; vowels++) {
dp[nValue][vowels] = dp[nValue][vowels-1] + dp[nValue-1][vowels];
}
}
return dp[n][5];
}
}
Approach 5: Math
영어로 설명하기가 좀 어려움
Intuition and Algorithm
The problem is a variant of finding Combinations. Mathematically, the problem can be described as, given 5 vowels (let k = 5), we want to find the number of combinations using only n vowels. Also, we can repeat each of those vowels multiple times.
In other words, from k vowels (k = 5), we can choose n vowels with repetition. Denoted as k \choose n, the formulae for Combination with Repetition is given by,
k \choose n = \frac{(k + n - 1)!}{ (k - 1)! n!}
We know that the k value is 5 as there are always 5 vowels to choose from. Substituting k as 5 in above formulae,
5 \choose n = \frac{(n+4) \cdot (n+3) \cdot (n+2) \cdot (n+1)}{24}
The derivation can be illustrated as follows.
class Solution {
public int countVowelStrings(int n) {
return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
}
}
Complexity Analysis
-
Time Complexity: \mathcal{O}(1), as the approach runs in constant time.
-
Space Complexity: \mathcal{O}(1), as the approach uses constant extra space.
leetcode.com/problems/furthest-building-you-can-reach/
Furthest Building You Can Reach - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
for(int i = 0; i < heights.length - 1; i++){
int diff = heights[i + 1] - heights[i];
if(diff > 0) { // Current building's height is less than the next building's height.
queue.add(diff); // Use ladder and add the difference.
if(queue.size() > ladders) { // If you ran out of ladders!
bricks -= queue.poll(); // Remove the smallest difference and use bricks instead
if(bricks < 0) {
return i; // Ops you ran out of the bricks and you stop here!
}
}
}
}
return heights.length - 1;
}
}
leetcode.com/contest/weekly-contest-213/problems/kth-smallest-instructions/
Account Login - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
곧 4개를 풀수있는날이 올것 같다.. 화이팅!
