Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Nabeel Keblawi
Simpler O(N^2) time solution with Python

Nabeel Keblawi

Oct 6, 2024

Here's what I did, no need for a second function or an additional for loop. Not sure why the solution recommended an O(N^3) solution when we could instead use two pointers to keep time complexity to O(N^2).

def searchTriplets(self, arr, target): arr.sort() count = 0 for i in range(0, len(arr) - 1): j = i + 1 # left pointer k = len(arr) - 1 # right pointer while j < k: if arr[i] + arr[j] + arr[k] < target: count += 1 if j == k - 1: k = len(arr) - 1 j += 1 else: k -= 1 return count

0

0

Comments
Comments