Leetcode Problem 2875. Minimum Size Subarray in Infinite Array

2875. Minimum Size Subarray in Infinite Array

Leetcode Solutions

Prefix Sum + Unordered Map + Sliding Window

  1. Calculate the total sum of the array nums and store it in sm.
  2. Calculate the remainder k of the target divided by sm.
  3. Calculate the prefix sum needed to reach the target p as sm - k.
  4. Calculate the number of full cycles sd as target / sm.
  5. Initialize an unordered map pre to store prefix sums with their corresponding indices.
  6. Initialize a variable tmp to keep track of the current prefix sum.
  7. Iterate over the array nums and update tmp with the current prefix sum.
  8. Check if tmp - k exists in the map pre. If it does, update the answer ans with the minimum length found so far.
  9. Check if tmp - p exists in the map pre. If it does, update ans with the minimum length considering the cycles.
  10. Update the map pre with the current prefix sum and index.
  11. Return ans if a subarray is found, otherwise return -1.
UML Thumbnail

Sliding Window

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...