Leetcode 2824: Count Pairs Whose Sum is Less than Target

Input: The input consists of an integer array nums and an integer target. The array nums has length n, and the integer target is a threshold value.

Example: nums = [2, -1, 3, 5, -2], target = 4

Constraints:

• 1 <= nums.length == n <= 50

• -50 <= nums[i], target <= 50

Output: Return the number of distinct pairs (i, j) where 0 <= i < j < n such that nums[i] + nums[j] < target.

Example: Output: 4

Constraints:

• The output should be a single integer representing the number of valid pairs.

Goal: The goal is to count the number of pairs of indices (i, j) that satisfy the condition nums[i] + nums[j] < target.

Steps:

• 1. Iterate over all pairs of indices (i, j) where i < j.

• 2. For each pair, check if nums[i] + nums[j] is less than the target.

• 3. Keep a count of the valid pairs.

Goal: The array nums has a length between 1 and 50, and the elements of nums as well as the target value are within the range [-50, 50].

Steps:

• 1 <= nums.length <= 50

• -50 <= nums[i], target <= 50

Assumptions:

• The input array nums is not empty, and there is always at least one valid pair when the input is valid.

• Input: nums = [2, -1, 3, 5, -2], target = 4

• Explanation: The valid pairs are (0, 1), (0, 2), (0, 4), and (1, 4), all of which have a sum less than the target.

Approach: To solve the problem, we can use a brute-force approach by checking all pairs of indices.

Observations:

• We are required to check all pairs of indices (i, j) where i < j.

• A brute-force solution works well for the constraints, as n is small (<= 50).

Steps:

• 1. Initialize a variable ans to 0.

• 2. Use a nested loop to iterate through all pairs of indices (i, j).

• 3. If nums[i] + nums[j] is less than the target, increment ans.

• 4. Return the value of ans as the final result.

Empty Inputs:

• The input array will never be empty as per the constraints.

Large Inputs:

• The solution should efficiently handle the maximum array size of 50.

Special Values:

• When all elements in the array are the same, the number of valid pairs depends on the target.

Constraints:

• Since n is small (<= 50), a brute-force solution is acceptable.

  int countPairs(vector<int>& nums, int target) {
  int ans = 0;
  for(int i = 0; i < nums.size(); ++i){
      for(int j = i + 1; j < nums.size(); ++j){
          if(nums[i] + nums[j] < target) ans++;
      }
  }
  return ans;
  }

1 : Function Definition

  int countPairs(vector<int>& nums, int target) {

The function 'countPairs' is defined, accepting a vector of integers 'nums' and an integer 'target' as parameters.

2 : Variable Initialization

  int ans = 0;

A variable 'ans' is initialized to 0, which will be used to keep track of the number of pairs whose sum is less than 'target'.

3 : Outer Loop

  for(int i = 0; i < nums.size(); ++i){

The outer loop begins, iterating over each element of the vector 'nums' from index 0 to the last element.

4 : Inner Loop

      for(int j = i + 1; j < nums.size(); ++j){

The inner loop starts from index 'i + 1' and iterates through the elements after the current element of the outer loop, ensuring all pairs are checked.

5 : Condition Check

          if(nums[i] + nums[j] < target) ans++;

Check if the sum of the pair 'nums[i]' and 'nums[j]' is less than the 'target'. If true, increment the 'ans' counter.

6 : Return Statement

  return ans;

Return the final count of pairs that satisfy the condition.

Best Case: O(n^2)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: Since we need to check all pairs of indices (i, j), the time complexity is O(n^2).

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as we only need a few variables to track the count.

Leetcode 2824: Count Pairs Whose Sum is Less than Target

Explore →