My solutions to some leetcode problems
You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Luca Lombardo 92681d39e9 Refactor code for trapping rain water problem 4 weeks ago
2023_09_18 Refactor code for trapping rain water problem 4 weeks ago
2023_09_21 Refactor code for trapping rain water problem 4 weeks ago
2023_09_25 Refactor code for trapping rain water problem 4 weeks ago
2023_10_02 new prolem solved 3 months ago
2023_10_05/frogs-and-mosquitos Refactor code for trapping rain water problem 4 weeks ago
2023_10_09 not completed, still need to be fixes. Not fully working/tested 7 months ago
2023_10_12 new problems solved, fixed old problems 7 months ago
2023_10_16/update-the-array new problems solved, fixed old problems 7 months ago
2023_11_09 new problem 6 months ago
2023_11_13/subset-sum subset-sum DP solution, plus extra improvement 6 months ago
2023_11_16/longest-increasing-subsequence longest increasing subsequence DP solution 6 months ago
2023_11_30 new prolem solved 3 months ago
.gitignore added dir in gitignore 6 months ago
README.md Refactor code for trapping rain water problem 4 weeks ago

README.md

Solutions in Rust for some competitive programming problems

Created for the "Competitive Programming" course (academic year 23/24) at the Department of Computer Science of the University of Pisa.

Course Page: https://pages.di.unipi.it/rossano/competitive/

Time spent on the project

wakatime

List of problems

  • Kadane's Algorithm

    • Idea: We want to find the maximum subarray sum in an array of integers. It works by iterating through the array and keeping track of the maximum sum seen so far and the maximum sum ending at the current index. At each index, the algorithm compares the current element with the maximum sum ending at the previous index plus the current element. If the current element is greater, then the maximum sum ending at the current index is just the current element. Otherwise, the maximum sum ending at the current index is the sum of the maximum sum ending at the previous index and the current element. The algorithm also keeps track of the maximum sum seen so far, which is the maximum of all the maximum sums ending at each index. The final result is the maximum sum seen so far.
  • Trapping Rain Water

    • The strategy used to solve this problem is the two-pointer approach. We use two pointers, one at the beginning and one at the end of the array. We also keep track of the maximum height of the left and right sides. We then move the pointers towards each other, updating the maximum height as we go. If the maximum height of the left side is less than the maximum height of the right side, we know that we can trap water on the left side. Similarly, if the maximum height of the right side is less than the maximum height of the left side, we know that we can trap water on the right side. We keep adding the trapped water to the result until the pointers meet.
  • Search for a peak in an (unsorted) array

    • The idea is to use a modified version of the binary search and observe that in there always will be a peak element (the worst case is a monotonically increasing/decreasing sequence, and in that case the peak will be the last/first element). So we just check if nums[mid] is greater than nums[mid+1] or not. If it is, we can discard the right part of the array, otherwise we can discard the left part of the array. We will always move towards the direction of the peak. It's important to note that nums[-1] = nums[n] = -∞ and that nums[i] != nums[i+1] for all i.
  • Maximum Path Sum

  • Hands-On 1

  • Frogs and Mosquitoes

  • Check if All the Integers in a Range Are Covered

  • Longest k-Good Segment

  • Continuous Subarray Sum

  • Update the array

  • Nested segments

  • Powerful array

  • Longest Common Subsequence

  • Minimum Number of Jumps

  • Hands-On 2

  • Subset Sum

  • Longest increasing subsequence

  • Longest bitonic Sequence

  • N meetings in one room

  • Wilbur and array

  • Woodcutters

  • IsBipartite

  • Hands-On 3

Theory and algorithms