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

0% completed

Vote For New Content
Amir Roshanaei
Why the solutions complexity can't be just O(n)?

Amir Roshanaei

May 27, 2023

I'm using the below approach using two-pointers and using HashSet and the complexity is O(n) in both time and space, I don't understand why it should follow that approach in the solution to bring the complexity to O(n^3)

import java.util.*; class Solution { public static Set<List<Integer>> findSubarrays(int[] arr, int target) { Set<List<Integer>> result = new HashSet<>(); int left = 0; int right = left + 1; while (right < arr.length) { int product = arr[right] * arr[left]; if (product < target) { result.add(List.of(arr[left])); result.add(List.of(arr[right])); result.add(Arrays.asList(arr[left], arr[right])); } else { result.add(List.of(arr[right])); } left++; right++; } return result; } public static void main(String[] args) { System.out.println( Solution.findSubarrays(new int[] { 2, 5, 3, 10 }, 30)); System.out.println( Solution.findSubarrays(new int[] { 8, 2, 6, 5 }, 50)); } }

0

0

Comments
Comments