373rd LeetCode Weekly Contest Experience
ABOUT THE CONTEST:
In this Contest, there are a total of 4 problems, and 1 hours and 30 minutes are given to solve this problem.
For each wrong submission, there was a 10-minute extra penalty
Bonus Prizes
Rank |
Prize |
---|---|
1st |
Apple HomePod mini |
2nd |
Logitech G903 LIGHTSPEED Gaming Mouse |
3rd – 5th |
Backpack |
6th – 20th |
Water bottle and Notebooks |
Only LC-US accounts are eligible for the bonus rewards. After the ranking is finalized, a LeetCode team member will reach out to you through email regarding the gift!
OVERVIEW OF THE QUESTIONS:
I was able to solve first two problems out of 4 problems in these contests.
Problem Name |
Difficulty |
Pre-requisite |
Approx time to solve by me |
number of submissions by me |
---|---|---|---|---|
Matrix Similarity After Cyclic Shifts |
Easy |
Array, Math, Matrix |
5 – 10 min |
1 |
Count Beautiful Substrings I |
Medium |
String, Prefix Sum |
10 – 15 min |
1 |
Make Lexico-graphically Smallest Array by Swapping Elements |
Medium |
Array, Sorting |
15 – 20 min |
2 |
Count Beautiful Substrings II |
Hard |
Number Theory, Hash Table, Prefix Sum, Sorting |
45-60 min |
2 |
LET’S DISCUSS THE QUESTIONS:
Que 1) Matrix Similarity After Cyclic Shifts
My Experience: As usual, the first question was quite easy, the problem statement was straightforward and it took me around 5 minutes to type the solution, for someone with fast typing speed this question could have been solved within a minute or two.
Accepted Solution: Firstly, I reduce k shifts to (k % n) shifts as after n shifts the matrix will become similar to the initial matrix for this I stored original matrix into temporary matrix & perform k left shift on even indexed rows and k right shifts on odd indexed rows then compared whether temp is equal or not with the original matrix. Time Complexity O(m*n).
Que 2) Count Beautiful Substrings Part I
My Experience: This was a design problem in which we have to implement 2 functions, and it took me around 12 minutes to solve this question.
Accepted Solution: To solve this problem I iterate over all substrings and maintain the frequencies of vowels and consonants. Find Consonants and Vowels -> c, v And Perform the check c == v & ( c * v ) % k == 0. We do not actually need to create substring. We only require the number of vowels and consonants in it. Hence we can convert this question into sliding window.
Que 3) Make Lexicographically Smallest Array by Swapping Elements
My Experience: This question is a slightly difficult for me and I could not able to solve it in contest time. But after constest completed I read the editorial & solve it within 15 minutes.
Accepted Solution: I created Tuples [array[i], index_of(array[i]) -> i] -> [a[i], i] And sort array in increasing manner. Then group the elements such that difference to its neighbor is <=k. We get certain sorted groups. For result to be in lexicographically smallest condition, elements in result should occur in same manner as they occur in groups. With the help of index stored in tuples, we re-arrange elements in original array.
Que 4) Count Beautiful Substrings Part II
My Experience : This question is similar to Que 2 But there was change in constraints. I could not able to solve it within the time. Initially my solution Time Limit Exceed. After thinking long time I could able to solve it within required time
Accepted Solution : I construct a prefix diff[i] of differences between the number of seen vowels and the number of seen consonants for the first i letters. Given that diff[i] = seen_vowels[i] – seen_consonants[i], the equality between the number of vowels and consonants in the substring s[i:j+1] is the same as diff[i] = diff[j]. So checking all substrings with equal number of vowels and consonants amounts to finding all string positions i for which diff[i] has the same value. This can be done using hashing of previously seen positions.
Conclusion:
At the end I was able to solve 2 problem out of 4 problem. For me last two problem was difficult, I required more time to solve this last questions.
All the best for upcoming contest.