Description:
This PR introduces a function LongestSubsetWithZeroSum that calculates the length of the longest subarray with a sum of zero in an input vector. The algorithm uses a hash map to optimize the time complexity, improving it from a brute-force solution to a more efficient 𝑂(𝑛) approach.
Key Changes:
Implemented the LongestSubsetWithZeroSum function.
Optimized the subarray search using a prefix sum and hash map to track cumulative sums.
Added test cases in the main function to validate the logic with an example array.
Performance:
Time Complexity: O(n), where n is the size of the input array.
Space Complexity: O(n) due to the use of an unordered map for storing cumulative sums.
Testing:
Tested with example array: {6, 1, -1, 2, -1, 4, -5, -5}.
Verified that the output is correct, returning the length of the longest subarray with a sum of zero.
Description: This PR introduces a function LongestSubsetWithZeroSum that calculates the length of the longest subarray with a sum of zero in an input vector. The algorithm uses a hash map to optimize the time complexity, improving it from a brute-force solution to a more efficient 𝑂(𝑛) approach.
Key Changes: Implemented the LongestSubsetWithZeroSum function. Optimized the subarray search using a prefix sum and hash map to track cumulative sums. Added test cases in the main function to validate the logic with an example array.
Performance: Time Complexity: O(n), where n is the size of the input array. Space Complexity: O(n) due to the use of an unordered map for storing cumulative sums.
Testing: Tested with example array: {6, 1, -1, 2, -1, 4, -5, -5}. Verified that the output is correct, returning the length of the longest subarray with a sum of zero.