LeetCode, Hard, last two problems: 2809. Min Time to Make Array Sum At Most x & 2813. Max Elegance of a K-Length Subseq
2813. Max Elegance of K-Length Subseq: Swift code for elegantly selecting unique k-length subsequences with profit and categories. Solution uses sorting and iteration. Time: O(nlogn), Space: O(n).
LeetCode 2612 (Hard). Minimum Reverse Operations. Swift. BFS. O(n+k). O(n)
The algorithm follows a breadth-first search (BFS) approach to determine the minimum number of reverse operations needed to bring the 1 to each position in the array.
LeetCode 956 (Hard). Solution of the day. Tallest Billboard. Swift. DP
The code uses dynamic programming to solve the problem. It maintains a dictionary dp, where the keys represent the possible height differences between the two billboards, and the values represent the maximum sum of heights achieved for each height difference.
LeetCode 125. Valid Palindrome
Очередная задачка уровня Easy, но с довольно низким показателем Acceptance (44.4%). Что выражается в достаточно обширном наборе граничных случаев, некоторые из которых делают больно 🙂
LeetCode 13. Roman to Integer
Приятная задачка выпала в поиске – хоть и easy, а сделать интересно. Какая-то “практическая применимость” в ней видится.
LeetCode 2801 (Hard, Acceptance Level 14.5%). Count Stepping Numbers in Range. DP. Handles large inputs (10^9 + 7)
The Swift solution uses dynamic programming to solve the problem. The rec function recursively calculates the count of stepping numbers based on certain conditions. The dp array is used to store previously computed results, which helps avoid redundant calculations and improves efficiency.
LeetCode 2532 (Hard++, Extra Category, Amazon). Time to Cross a Bridge. Swift
Overflow checks have been taken into consideration. The maximum time to move a box is at most 4 * 1000 (four steps to move the box, each taking 1000 time). With at most 1e4 boxes, the total time is at most 4e7, ensuring the solution is safe.
LeetCode 2790 (Hard). Maximum Number of Groups With Increasing Length. Solution of the day. O(N logN). Math
The time complexity of this solution is dominated by the sorting step, making it O(N logN), where N is the length of the input array usageLimits. The rest of the operations involve simple arithmetic and comparisons, which take linear time. Therefore, the overall time complexity of the function is O(N logN).