## Amazon Interview Question

Dev Leads**Country:**United States

I think that the idea here is to do this in O(N) as the brute force algorithm take O(N^2). We can achieve an O(N) solution by have 1 loop which runs over the array and looks over a window of the array. This will use the fact that the array contains non negative numbers.

```
def find_continued_sub_arr(A, S):
i, j, sum = 0, 0, 0
while i < len(A) and j < len(A) and sum != S:
sum += A[j]
if sum < S:
j += 1
elif sum > S:
if i < j:
sum -= A[i]
i += 1
else:
i = j = i + 1
return None if sum != S else (i,j)
```

/******************************************************************************

Online C Compiler.

Code, Compile, Run and Debug C program online.

Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <stdio.h>

int main()

{

int temp,idx,i,start,end;

idx =0;

start = 0;

end = 0;

int a[]={2,0,1,2,4,4};

for (i=0;i<sizeof(a);i++)

{

temp += a[i];

if(temp > 7)

{

i = ++start;

temp = a[i];

}

if (temp == 7)

{

end =i;

++idx;

break;

}

}

if(idx == 0)

printf("xxx");

else

printf("%d %d",start, end);

return 0;

}

```
/******************************************************************************
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
int main()
{
int temp,idx,i,start,end;
idx =0;
start = 0;
end = 0;
int a[]={2,0,1,2,4,4};
for (i=0;i<sizeof(a);i++)
{
temp += a[i];
if(temp > 7)
{
i = ++start;
temp = a[i];
}
if (temp == 7)
{
end =i;
++idx;
break;
}
}
if(idx == 0)
printf("xxx");
else
printf("%d %d",start, end);
return 0;
}
```

Since it says continuous sub array so i think it is asking for sonsecutive elements which gives the target.

```
def cont(array, s):
i, j, su = 0,0,0
while i<len(array) and j<len(array):
su += array[j]
if su==s:
if i!=j:
return i,j
else:
return i
if su < s:
j += 1
if su > s:
su -= array[i]
i += 1
j += 1
return
array = [7,8,3,2,1,5,4]
print(cont(array, 24))
```

private static int[] findSubArray(int[] array, int sum) {

int start = 0, end = 0;

int sum_temp = array[start];

for (;end<array.length;end++) {

if (end > 0) {

sum_temp += array[end];

}

if (sum_temp > sum) {

while (sum_temp > sum) {

sum_temp -= array[start];

start++;

}

}

if (sum_temp == sum) {

return Arrays.copyOfRange(array, start, end+1);

}

}

return new int[0];

}

Time complexity O(N)

```
private static int[] findSubArray(int[] array, int sum) {
int start = 0, end = 0;
int sum_temp = array[start];
for (;end<array.length;end++) {
if (end > 0) {
sum_temp += array[end];
}
if (sum_temp > sum) {
while (sum_temp > sum) {
sum_temp -= array[start];
start++;
}
}
if (sum_temp == sum) {
return Arrays.copyOfRange(array, start, end+1);
}
}
return new int[0];
}
```

Sliding window - O(n)

```
def sub_array_with_sum(arr: [int], sum: int) -> [int]:
window_sum = arr[0]
window_range = (0, 0)
if window_sum == sum:
return [0]
start = 1
for i in range(start, len(arr)):
window_sum += arr[i]
window_range[1] = i
while window_sum > sum:
window_sum -= arr[window_range[0]]
window_range[0] += 1
if window_sum == sum:
res = []
for j in range(window_range[0], window_range[1] + 1):
res.append(j)
return res
return [-1]
```

```
public class ContiguousSubarrayWithSum {
public static void main(String[] args) {
int[] array = {2,6,1,2,4,4};
int k = 7;
findSubArray(array,k);
}
public static void findSubArray(int[] array, int k){
int start = 0;
int sum = 0;
for (int i =0; i < array.length ; i++){
while (start < i && sum > k ){
sum -= array[start++];
}
if(sum == k){
int end = i-1;
System.out.println("Subarray found at : "+ start+ " "+ end);
}
if (i < array.length){
sum+= array[i];
}
}
}
}
```

def find_sub_array(a, s):

- ash February 06, 2020for i in range(len(a)):

for j in range(len(a), i, -1):

sub = a[i:j]

total = sum(sub)

if total == s:

return sub

return None