- Denisse's Newsletter
- Posts
- I know you got the solution š Want to check?
I know you got the solution š Want to check?
Denisse Damian
January 26, 2024
Hi, welcome back!
You made it this far, keep up the great work!
Editorial for the problem: 1099. Two Sum Less Than K
Return the maximum sum of distinct pairs in the array such that the sum is less than k. If no such pair exists, return -1.
Before you read this email, make sure youāve tried the solution on your own.
What would the time complexity of using a two-pointer solution be?
What would the time complexity of using two-pointers be?Remember the array is not sorted |
The key to being able to use this technique is toā¦. sort the array!
The first step we take is to sort the array! Sorting an array of N elements using a standard sorting algorithm (like the one used in Python's sorted function) has a time complexity of O(N log N).
Initialize two pointers:
L = 0
R = Array.size() - 1
maxSum=-1 (In case we donāt find any pairs)
The left pointer can only move to the right, and the right pointer can only move to the left.
At each step of the algorithm, we calculate the sum of array[L] + array[R].
If the sum is less than 'k', update the maximum sum and move the 'left' pointer to the right to explore larger sums.
If the sum is greater than or equal to 'k', move the 'right' pointer to the left to decrease the sum.
Letās dig in with an exampleā¦
Day 4 Example
Solution:
Day 4 Solution
Letās now add it to our LeetCode Trackerā¦
| Leetcode # | Summary | Naive Solution | Optimization | Big O Notation |
|---|---|---|---|---|
| 1099 | Two Sum Less Than K | Use two nested for loops to find pairs whose sum is less than k. | Sort the array and use two pointers to find the maximum sum of distinct pairs less than k. | Naive Solution: Memory: O(1) Time Complexity: O(N^2) Optimization: Memory: O(1) Time Complexity: O(N log N) |
Enjoy your weekend and see you next Monday with a new challenge!
Denisse
Reply