Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
First Approach
3.1.
CODE
3.1.1.
Input
3.1.2.
Output
3.1.3.
Time Complexity
4.
Optimal Solution
4.1.
CODE
4.1.1.
Input
4.1.2.
Output
5.
Frequently Asked Questions
5.1.
What is a sub-array in Java?
5.2.
What is the difference between Subarray and subsequence?
5.3.
How many Subarrays are in an array?
5.4.
Are the substring and Subarray the same?
5.5.
Are subsequence and substring the same?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Smallest subarray with sum greater than a given value

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Every coding interview is built on the foundation of arrays. As a result, a thorough knowledge of the subject is essential. But there's nothing to be concerned about. We're here to assist, and today we'll tackle the well-known interview question, "Smallest subarray with a total greater than a specific amount." This is a simple array-based issue. So, consider the issue statement of the question: 'Smallest subarray with a total greater than a particular figure.'

Also See, Array Implementation of Queue

Understanding the Problem

Find the smallest Subarray whose total is bigger than the provided integer given an array and an integer.

Examples:
arrA[] = { 1, 5, 20, 70, 8}
Integer = 97
Output : Min Length = 3 Subarray = [20, 70, 8]

arrA[] = { 1, 10, 3, 40, 18}
Integer = 50
Output : Min Length = 2 Subarray = [40, 18]
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

First Approach

Two stacked loops are a straightforward solution. The outer loop chooses a starting element, while the inner loop treats all items to the right of the current start as finishing elements. If the current length is shorter than the previous shortest length, update the result whenever the sum of parts between the current start and finish exceeds the supplied number.

The basic technique is implemented as follows.

CODE

# include <iostream>
using namespace std;
// Returns the length of the smallest Subarray whose sum exceeds x. If no // subarray with the supplied sum exists, returns n+1.
int smallest_SubWithSum(int arr[], int size, int x)
{
// Set the length of the smallest subarray to n+1.
int mn_ln = size + 1;
// Choose a starting position for each element.
for (int strt=0; start<size; strt++)
{
 // Start the sum with the current start.
 int crr_sm = arr[strt];
 // If the first element is bigger,
 if (crr_sm > x) return 1;
 // Experiment with alternative finishing positions for the 
// present start.
 for (int nd=strt+1; nd<size; nd++)
 {
  // add the last element to the current total
  crr_sm += arr[nd];
  // If the total exceeds x and the length of this //subarray is 
// less than the current smallest length, the smallest length should be //updated (or result)
  if (crr_sm > x && (nd - strt + 1) < mn_ln)
   mn_ln = (nd - strt + 1);
 }
}
return mn_ln;
}

/* To test the aforementioned function, use the driver software.*/
int main()
{
int rr1[] = {1, 4, 45, 6, 10, 19};
int x_1 = 51;
int size_1 = sizeof(rr1)/sizeof(rr1[0]);
int rs1 = smallest_SubWithSum(rr1, size_1, x_1);
if(rs1 == size_1+1)
cout << "Not possible"<<endl;
else
 cout << rs1 << endl;
int rr2[] = {1, 10, 5, 2, 7};
int size_2 = sizeof(rr2)/sizeof(rr2[0]);
x_2 = 9;
int rs2 = smallest_SubWithSum(rr2, size_2, x_2);
if(rs2 == size_2+1)
cout << "Not possible"<<endl;
else
 cout << rs2 << endl;
int rr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
int size_3 = sizeof(arr3)/sizeof(arr3[0]);
x_3 = 280;
int res3 = smallestSubWithSum(arr3, size_3, x_3);
if(rs3 == size_3+1)
cout << "Not possible"<<endl;
else
 cout << rs3 << endl;
return 0;
}

Input

1, 4, 45, 6, 10, 19
51
1, 10, 5, 2, 7
9
1, 11, 100, 1, 0, 200, 3, 2, 1, 250
280

Output

3
1
4

Time Complexity

The time complexity of the above approach is clearly O(n2).

Optimal Solution

This issue is O(n) time to solve. The aim is to utilize a single loop to keep track of the current total and the Subarray's start and endpoints. The following is the procedure:

CODE

// O(n) solution for finding the smallest Subarray with a sum
// larger than the sum
#include <iostream>
using namespace std;
// Returns the length of the smallest Subarray whose sum exceeds the sum. // Suppose no subarray with the supplied sum exists returns size+1.
int smallestSubWithSum(int arr[], int size, int sum)
{
// Set the current sum and the minimum length.
int crr_sm = 0, mn_ln = size + 1;
// Set up the beginning and end indexes.
int strt = 0, nd = 0;
while (nd < size) {
 // Continue to add array members as long as the current total                      // is less <=sum.
 while (crr_sm <= sum && nd < size)
  crr_sm += rr[nd++];
 // If current sum becomes >x.
 while (crr_sm > x && strt < n) {
  // change min length if required
  if (nd - strt < mn_ln)
   mn_ln = nd - strt;
  // remove start elements
  crr_sm -= rr[strt++];
 }
}
return mn_ln;
}
/* To test the aforementioned function, use the driver software.*/
int main()
{
int rr1[] = {1, 4, 45, 6, 10, 19};
int x_1 = 51;
int size_1 = sizeof(rr1)/sizeof(rr1[0]);
int rs1 = smallest_SubWithSum(rr1, size_1, x_1);
if(rs1 == size_1+1)
cout << "Not possible"<<endl;
else
 cout << rs1 << endl;
int rr2[] = {1, 10, 5, 2, 7};
int size_2 = sizeof(rr2)/sizeof(rr2[0]);
x_2 = 9;
int rs2 = smallest_SubWithSum(rr2, size_2, x_2);
if(rs2 == size_2+1)
cout << "Not possible"<<endl;
else
 cout << rs2 << endl;
int rr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
int size_3 = sizeof(arr3)/sizeof(arr3[0]);
x_3 = 280;
int res3 = smallestSubWithSum(arr3, size_3, x_3);
if(rs3 == size_3+1)
cout << "Not possible"<<endl;
else
 cout << rs3 << endl;
return 0;
}

Input

1, 4, 45, 6, 10, 19
51
1, 10, 5, 2, 7
9
1, 11, 100, 1, 0, 200, 3, 2, 1, 250
280

Output

3
1
4

Time Complexity
The time complexity of the above approach is clearly O(n).

Frequently Asked Questions

What is a sub-array in Java?

A component or segment of an array is frequently referred to as a subarray. An array is a collection of variables defined by a programmer. Rather than generating several variables, the programmer might represent a single array with various labels.

What is the difference between Subarray and subsequence?

A subarray or substring must be continuous, while a subsequence does not have to be. Sequences do not have to be placed in the same order as the original sequences. However, both contiguous subsequence and Subarray are the same thing.

How many Subarrays are in an array?

In an array of size N, the total number of subarrays is N * (N + 1) / 2. The total number of odd continuous items in the array is equal to the number of subarrays having an odd product.

Are the substring and Subarray the same?

In the context of strings, a substring is the same as a subarray. For example, the substrings of the string "ara" are "a," "r," "ar," "ra," "ara," and "." Note that a substring is simply a subarray made up entirely of characters.

Are subsequence and substring the same?

A Substring removes characters from a string in a continuous order between two given indices. Subsequence, on the other hand, maybe created from another sequence by removing part or all of the components in between while keeping the relative order of the elements in the original sequence.

Conclusion

So that's the end of the article Smallest subarray with a sum greater than a given value.

After reading about the Smallest Subarray with a sum greater than a given value, are you not feeling excited to read/explore more about arrays such as the sum of two arraysmerge K sorted arrays, etc.  ? Don't worry; Coding Ninjas has you covered.

Recommended problems -

 

However, you may want to pursue our premium courses to give your job an advantage over the competition!

With our Coding Ninjas Studio Guided Path, you may learn about Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and more! If you wish to test your coding abilities, check out the mock test series and enter the contests on Coding Ninjas Studio.However, suppose you've just started school and are looking for answers to concerns raised by digital behemoths such as Amazon, Microsoft, Uber, and others, as part of your placement preparations. In that case, you must evaluate the obstaclesinterview experiences, and interview package in this case. Please vote for our blogs if you find them valuable and exciting.

Happy studying!

Previous article
Generate all Possible Sorted Arrays from Alternate Elements of Two Given Sorted Arrays
Next article
Program for Mean and Median of an unsorted array
Live masterclass