Solving DSA problems from leetcode
You're to find the closest number to zero in a given array or a python list
You're given two strings word1 and word2. Merge these strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.
Covert a string of roman numerals to an integer.
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
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.
Summary Ranges LeetCode 228
This problem was quite challenging, but I was able to solve it fairly easily. Even though the solution has two while loops, it surprisingly has a time complexity of O(n).
Took a crack at Leetcode 238 (Product of Array Except Self) for the first time. Coming up with a solution was a breeze—probably because I totally ignored the constraints. 😅 Both of my solutions are O(n^2), which isn't exactly ideal, but hey, they work!
I found this code online that seemed like a good explanation, but I’m still not sure I fully understand it.
Here are my first solutions, though they don't follow the constraints yet
.png)
.png)
I tried Leetcode 56 (Merge Intervals), and my solution was accepted with a time complexity of O(NlogN). It ran in 140ms but only beat 5.53% of submissions, which was surprising. The code is pretty straightforward since I'm still learning 😅. Took a look at the top solutions and found some interesting approaches.
I refactored the code I used to solve this problem. The if condition checks whether the merged list is empty or if the end of the last interval in the merged list is less than the start of the current interval. If there’s no overlap, the current interval is appended to the merged list. Otherwise, the intervals are merged by updating the end of the last interval in the merged list to be the maximum of the current interval’s end and the last interval’s end.
I solved LeetCode 54, the spiral matrix problem. My code ran in 32ms, beating 76.71% of submissions. It has a time complexity of O(m*n) and uses constant space. I used a combination of while and for loops—the while loop checks if the length of the answer list is still less than the total number of elements in the matrix, while the for loops append each number to the answer list. To avoid repetition, I implemented a wall mechanism, where after each spiral, the boundaries (walls) decrease, preventing duplicate additions. This fixed the issue I had in my first attempt.