Efficient approach: The idea is similar to Find a triplet that sum to a given value.
Sort the given array first.
Start fixing the greatest element of three from the back and traverse the array to find the other two numbers which sum up to the third element.
Take two pointers j(from front) and k(initially i-1) to find the smallest of the two number and from i-1 to find the largest of the two remaining numbers
If the addition of both the numbers is still less than A[i], then we need to increase the value of the summation of two numbers, thereby increasing the j pointer, so as to increase the value of A[j] + A[k].
If the addition of both the numbers is more than A[i], then we need to decrease the value of the summation of two numbers, thereby decrease the k pointer so as to decrease the overall value of A[j] + A[k]. Time Complexity: O(N^2)
Auxiliary Space: O(1)
Description
Please include a summary of the changes and the related issue(s) this pull request addresses. Include any relevant context or background information.
Fixes: #[issue_number] (replace with the issue number, if applicable)
Use [x] to represent a checked (ticked) box.✅
Use [ ] to represent an unchecked box.❌
Type of Change
[ ] Question Added
[ ] Solution Added
[ ] Other (please specify):
Checklist
[ ] I have performed a self-review of my code.
[ ] I have commented my code, particularly in hard-to-understand areas.
[ ] I have made corresponding changes to the documentation (if applicable).
[ ] My changes generate no new warnings.
[ ] I have added tests to cover my changes (if applicable).
[ ] All new and existing tests pass.
Additional Notes
Please add any other information that is relevant to this pull request, including potential risks, alternative solutions considered, or future improvements.
Efficient approach: The idea is similar to Find a triplet that sum to a given value.
Sort the given array first.
Start fixing the greatest element of three from the back and traverse the array to find the other two numbers which sum up to the third element.
Take two pointers j(from front) and k(initially i-1) to find the smallest of the two number and from i-1 to find the largest of the two remaining numbers
If the addition of both the numbers is still less than A[i], then we need to increase the value of the summation of two numbers, thereby increasing the j pointer, so as to increase the value of A[j] + A[k].
If the addition of both the numbers is more than A[i], then we need to decrease the value of the summation of two numbers, thereby decrease the k pointer so as to decrease the overall value of A[j] + A[k]. Time Complexity: O(N^2) Auxiliary Space: O(1)
Description
Please include a summary of the changes and the related issue(s) this pull request addresses. Include any relevant context or background information.
Fixes: #[issue_number] (replace with the issue number, if applicable)
Use [x] to represent a checked (ticked) box.✅ Use [ ] to represent an unchecked box.❌
Type of Change
Checklist
Additional Notes
Please add any other information that is relevant to this pull request, including potential risks, alternative solutions considered, or future improvements.