Skip to content

1498. Number of Subsequences That Satisfy the Given Sum Condition #1866

Answered by mah-shamim
mah-shamim asked this question in Q&A
Discussion options

You must be logged in to vote

We need to count the number of non-empty subsequences in an array where the sum of the minimum and maximum elements in each subsequence is less than or equal to a given target. Given the constraints, a brute-force approach is infeasible, so we use sorting and a two-pointer technique to efficiently count valid subsequences.

Approach

  1. Sort the Array: Sorting helps in efficiently determining the valid subsequences by allowing us to use two pointers to find the range of elements that can form valid subsequences with a given minimum element.
  2. Precompute Powers of Two: Since the number of valid subsequences for a given range can be 2(j-i) (where i is the starting index and j is the ending index …

Replies: 1 comment 2 replies

Comment options

You must be logged in to vote
2 replies
@topugit
Comment options

topugit Jun 29, 2025
Collaborator

@mah-shamim
Comment options

mah-shamim Jun 29, 2025
Maintainer Author

Answer selected by topugit
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Category
Q&A
Labels
question Further information is requested medium Difficulty
2 participants