Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given a list of numbers, count the number of triplets having a sum less than a given target.

```
{
"target": 4,
"numbers": [5, 0, -1, 3, 2]
}
```

Output:

```
2
```

`{numbers[1], numbers[2], numbers[3]}`

and `{numbers[1], numbers[2], numbers[4]}`

are the triplets having sum less than 4.

```
{
"target": 7,
"numbers": [2, 2, 2, 1]
}
```

Output:

```
4
```

`{numbers[0], numbers[1], numbers[2]}`

, `{numbers[0], numbers[1], numbers[3]}`

, `{numbers[0], numbers[2], numbers[3]}`

and `{numbers[1], numbers[2], numbers[3]}`

are the triplets having sum less than 7.

The original array's indexes identify a triplet. Therefore, any two triplets will differ if they are denoted by a different triplet of indexes, even if the values present at those indexes are the same. Please observe `Example Two`

for more details on this.

Constraints:

- 3 <= size of the input list <= 10
^{3} - -10
^{5}<= any element of the input list <= 10^{5} - -10
^{9}<= target number <= 10^{9}

```
/*
Asymptotic complexity in terms of length of the input list \`n\`:
* Time: O(n * n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
int count_triplets(int target, vector<int> &numbers) {
sort(numbers.begin(), numbers.end());
int n = numbers.size();
int result = 0;
for (int i = 0; i < n; i++) {
int low = i + 1, high = n - 1;
while (low < high) {
int triplet_sum = numbers[i] + numbers[low] + numbers[high];
if (triplet_sum < target) {
result += high - low;
low++;
}
else {
high--;
}
}
}
return result;
}
```

We hope that these solutions to the 3 sum smaller problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

Given a list of numbers, count the number of triplets having a sum less than a given target.

```
{
"target": 4,
"numbers": [5, 0, -1, 3, 2]
}
```

Output:

```
2
```

`{numbers[1], numbers[2], numbers[3]}`

and `{numbers[1], numbers[2], numbers[4]}`

are the triplets having sum less than 4.

```
{
"target": 7,
"numbers": [2, 2, 2, 1]
}
```

Output:

```
4
```

`{numbers[0], numbers[1], numbers[2]}`

, `{numbers[0], numbers[1], numbers[3]}`

, `{numbers[0], numbers[2], numbers[3]}`

and `{numbers[1], numbers[2], numbers[3]}`

are the triplets having sum less than 7.

The original array's indexes identify a triplet. Therefore, any two triplets will differ if they are denoted by a different triplet of indexes, even if the values present at those indexes are the same. Please observe `Example Two`

for more details on this.

Constraints:

- 3 <= size of the input list <= 10
^{3} - -10
^{5}<= any element of the input list <= 10^{5} - -10
^{9}<= target number <= 10^{9}

```
/*
Asymptotic complexity in terms of length of the input list \`n\`:
* Time: O(n * n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
int count_triplets(int target, vector<int> &numbers) {
sort(numbers.begin(), numbers.end());
int n = numbers.size();
int result = 0;
for (int i = 0; i < n; i++) {
int low = i + 1, high = n - 1;
while (low < high) {
int triplet_sum = numbers[i] + numbers[low] + numbers[high];
if (triplet_sum < target) {
result += high - low;
low++;
}
else {
high--;
}
}
}
return result;
}
```

We hope that these solutions to the 3 sum smaller problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart

- Designed by 500 FAANG+ experts
- Live training and mock interviews
- 17000+ tech professionals trained

00

Days

:

00

Hrs

:

00

Mins

:

00

Secs