Banana.
Text
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
Example 1:Input: citations = [3,0,6,1,5] Output: 3
we could use brute force but that’s not what we are going to do
paper_counts = [0] * (n + 1)
if n=5
paper_counts = [0] * 6, then it means paper_counts = [0, 0, 0, 0, 0, 0]
for c in citations:
paper_counts[min(n, c)] += 1 , what happens here is that….
Input
citations = [3, 0, 6, 1, 5] ,n = 5, paper_counts = [0, 0, 0, 0, 0, 0]
Iteration 1
c = 3, min(5, 3) = 3, paper_counts[3] += 1
[0, 0, 0, 1, 0, 0]
This takes place in an iteration. Then we go backwards and stop when the h value and paper count are equal.
time complexity: O(n)
space complexity:O(n)
Text
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.
Find and return the maximum profit you can achieve.
Pretty simple, we just iterate and find the lower point and higher point, subtract them and add them to the profit
time complexity: O(n)
space complexity: O(1)
Text
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
so, what happens here is that ‘i’ is going to scan through the array and 'j’ is going to rewrite the array. 'i’ and 'j’ start from index 1, and if the previous element to i is similar to i then we increment the count, else the count remains 1. Now, if the count is less than or equal to 2, we overwrite with the element where 'i’ is standing, then increment j and at the end return j.
Time complexity: O(n)
space complexity:O(1)
Text
Switching from C to Python is super easy, barely an inconvenience.
Text
- postorder traversal (dfs)
- preorder traversal (dfs)
- Inorder traversal (dfs)
- level order traversal (bfs)
Text
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Consider the number of unique elements in nums to be k. After removing duplicates, return the number of unique elements k.
The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k - 1 can be ignored.
Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
This is VERY EASYY, I don’t even have to explain
time complexity: O(n)
space complexity: O(1)
Text
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Only I could copy a code from youtube and still make mistake brooo.
The explanation for this line , for z in range(m + n - 1, -1, -1)
The range(start, stop, step) function determines the loop’s bounds:
- Start (m + n - 1): The loop begins at the index m+n−1
- Stop (-1): The loop continues as long as z > -1. Therefore, the last value of z processed is 0.
- Step (-1): This indicates that the value of z decreases by 1 in each iteration.
Pretty easy to understand, if you look at this picture. Everything else is understandable if I just look at the code…
time complexity : O(m+n)
space complexity: O(1)
Text
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:string convert(string s, int numRows);
Example 1:Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR”
the no of [] is based on the no of rows given in the question.
The code makes sure we append in each row, then when we hit the row limit, we append in each row in reverse. then when we reach the first row, we change direction, and then we go back down. Finally, we join all these and give it as a single array named ret.
Easy, right???
time complexity: O(n)
space complexity: O(n+numRows)
Can someone tell me if the time complexity and space complexity is correct??
Text
You are given a sorted unique integer array nums.
A range [a,b] is the set of all integers from a to b (inclusive).
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.
Each range [a,b] in the list should be output as:
- “a->b" if a != b
- "a" if a == b
Example 1:Input: nums = [0,1,2,4,5,7] Output: ["0->2”,“4->5”,“7”]
only I could copy from youtube and still manage to get an error bruhh
We create an empty list ans. We set the first element of nums to be the ‘start’. while the next consecutive number to the start is the next index, increment the i value. When the next value is not correct in the next index, the if condition will check whether the start and the position where i is standing are the same; if not, they append the start and the num[i] with -> in between. If yes, directly append just the number to ans. Then an increment takes place within the first while loop to continue the process and return ans in the end.
easy to understand, but will i be able to write this in my own, prolly not…
Time complexity: O(n)
space complexity: O(1)
Text
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
This is how they showed on YouTube on how to do it with brute force.
This is how to do optimisation.I never understood optimisation because most of the time, my brain is like this is the best solution I can give, and I cannot do better. I understood this though…
So basically, we find the minimum price first and then find the profit, and if the profit is the maximum, return it.
This seems so simple, and I promise you I could never think of something like this. Like, how are people so brilliant bro!??
time complexity : changes from O(2^n) to O(n)
space complexity: O(1)
Text
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "“.
Example 1:Input: strs = ["flower”,“flow”,“flight”] Output: “fl”
I searched google and float(‘inf’) is used for setting a variable with an infinitely large value. Still, I copied from YouTube.
We are iterating through the list and finding the string with minimum length. Now we are iterating through each letter at the same time in all the words, while ensuring it is within the minimum length. If it’s not equal, we return up to that point (return s[:i]). If it’s equal, we just increment the i value.
time complexity: O(n*m), where n is the no of strings and m is the min length, since we only iterate till the min length
space complexity: O(1)