Number of Subsequences That Satisfy the Given Sum Condition

Number of Subsequences That Satisfy the Given Sum Condition - Problem

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element in the subsequence is less than or equal to target.

Since the answer may be too large, return it modulo 10⁹ + 7.

Note: A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,5,6,7], target = 9

› Output: 4

💡 Note: Valid subsequences: [3], [5], [6], [3,5]. Each has min + max ≤ 9. For [3]: 3+3=6≤9, [5]: 5+5=10>9 (invalid), [6]: 6+6=12>9 (invalid), [3,5]: 3+5=8≤9.

Example 2 — Smaller Target

$ Input: nums = [3,3,6,8], target = 10

› Output: 6

💡 Note: After sorting [3,3,6,8]: valid subsequences include [3], [3], [3,3], [3,6], [3,6] (different 3's), [3,3,6]. Min + max ≤ 10 for each.

Example 3 — All Valid

$ Input: nums = [2,3,3,4,6,7], target = 12

› Output: 61

💡 Note: Most subsequences are valid since target is large. Even [6,7] has 6+7=13>12, but many smaller combinations work.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
1 ≤ target ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,5,6,7] with target 9

Process

Check each subsequence's min + max against target

Output

Count of valid subsequences: 4

Key Takeaway

🎯 Key Insight: Sort first, then use two pointers to count 2^(right-left) subsequences efficiently

Asked in

G Google 15 f Facebook 12 A Amazon 8

The key insight is to sort the array first, then use two pointers to efficiently count valid subsequences. When nums[left] + nums[right] ≤ target, all 2^(right-left) subsequences containing nums[left] are valid. Best approach is Sort and Two Pointers. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Two Pointers	O(n log n)	O(1)	Sort array first, then use two pointers to count valid subsequences efficiently
Brute Force - Generate All Subsequences	O(n × 2^n)	O(n)	Generate all possible subsequences and check each one

Sort and Two Pointers — Algorithm Steps

Sort the input array
Use two pointers: left at start, right at end
For valid pair, count 2^(right-left) subsequences
Move pointers based on sum condition

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort [3,5,6,7] to enable two-pointer technique

Two Pointers

Use left=0, right=3 pointers to check sums

Count Subsequences

When valid, count 2^(right-left) subsequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize, int target) {
    const int MOD = 1000000007;
    qsort(nums, numsSize, sizeof(int), compare);
    
    // Precompute powers of 2
    long pow2[numsSize];
    pow2[0] = 1;
    for (int i = 1; i < numsSize; i++) {
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
    
    int left = 0, right = numsSize - 1;
    long result = 0;
    
    while (left <= right) {
        if (nums[left] + nums[right] <= target) {
            result = (result + pow2[right - left]) % MOD;
            left++;
        } else {
            right--;
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* start = strchr(line, '[');
    char* end = strchr(line, ']');
    *end = '\0';
    start++;
    
    char* token = strtok(start, ",");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), two-pointer scan takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for pointers and variables

✓ Linear Space

58.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler