Leetcode Problem 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Leetcode Solutions

Prefix Sum and Dynamic Programming

  1. Initialize a hashmap to store prefix sums with the initial entry (0, -1).
  2. Initialize variables for the current sum, the minimum length of a sub-array found so far (lsize), and the result (the minimum sum of lengths of two sub-arrays).
  3. Iterate through the array, updating the current sum and storing it in the hashmap with the current index as the value.
  4. During the iteration, check if the current sum minus the target exists in the hashmap. If it does, update lsize with the minimum length found so far.
  5. Check if there is a sub-array starting after the current index with a sum equal to the target. If such a sub-array exists and lsize is not infinity, update the result with the minimum value of the sum of both sub-array lengths.
  6. Return the result if it's not infinity; otherwise, return -1.
UML Thumbnail

Sliding Window Approach

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...