Repository navigation
Expand file tree
/
Copy pathBinarySubarrayWithSum.cpp
More file actions
120 lines (93 loc) · 2.65 KB
/
Copy pathBinarySubarrayWithSum.cpp
File metadata and controls
120 lines (93 loc) · 2.65 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/////////////////////// APPROACH 1: Prefix Sum + HashMap //////////////////////////
class Solution
{
public:
int numSubarraysWithSum(vector<int>& nums, int goal)
{
unordered_map<int, int> mp;
int prefixSum = 0, count = 0;
for (int i = 0; i < nums.size(); ++i)
{
prefixSum += nums[i];
if (prefixSum == goal)
count++;
if (mp.find(prefixSum - goal) != mp.end())
count += mp[prefixSum - goal];
mp[prefixSum]++;
}
return count;
}
};
/*
Approach:
- Maintain running prefix sum.
- If (prefixSum - goal) has occurred before, it means there's a subarray ending here with sum equal to goal.
- Add the frequency of (prefixSum - goal) to result.
Time: O(n)
Space: O(n)
*/
/////////////////////// APPROACH 2: AtMost(goal) - AtMost(goal - 1) //////////////////////////
class Solution
{
public:
int numSubarraysWithSum(vector<int>& nums, int goal)
{
return atMost(nums, goal) - atMost(nums, goal - 1);
}
int atMost(vector<int>& nums, int goal)
{
if (goal < 0) return 0;
int left = 0, right = 0, sum = 0, count = 0;
for (; right < nums.size(); ++right)
{
sum += nums[right];
while (sum > goal)
sum -= nums[left++];
count += (right - left + 1);
}
return count;
}
};
/*
Approach:
- Count number of subarrays with sum <= goal and subtract those with sum <= goal-1.
- This gives number of subarrays with exact sum == goal.
- Works only when elements are 0 or 1.
Time: O(n)
Space: O(1)
*/
/////////////////////// APPROACH 3: Sliding Window + Leading Zeros Trick //////////////////////////
class Solution
{
public:
int numSubarraysWithSum(vector<int>& nums, int goal)
{
int left = 0, right = 0, sum = 0, count = 0;
int zeroPrefix = 0;
while (right < nums.size())
{
sum += nums[right];
// Shrink window if sum > goal or leading zero
while (left < right && (sum > goal || nums[left] == 0))
{
if (nums[left] == 0)
zeroPrefix++;
else
zeroPrefix = 0;
sum -= nums[left++];
}
if (sum == goal)
count += zeroPrefix + 1;
right++;
}
return count;
}
};
/*
Approach:
- Binary array only (0s and 1s).
- Expand window, and on finding sum == goal, count number of leading zeros to capture all valid subarrays.
- More optimal than a naive sliding window that checks each subarray.
Time: O(n)
Space: O(1)
*/