CODEWITHSUNDEEP
arraysalgorithm
Ravi Gupta
Ravi Gupta

Reputation: 6480

Find two integers in a sorted array such that a - b = k

Given an integer k and an sorted array A (can consist of both positive and negative numbers), output 2 integers from A such that a-b=k in O(n) time and O(1) space

O(n logn) Solution:

  1. Traverse the array: O(n)
  2. For element a[i], find a[i]+k in the array using binary search :O(log n)

Total Time: O(n logn)

O(n) Solution:

  1. Store all elements of the array in a Hash Table: O(n)
  2. For element a[i], check whether a[i]+k in the hash table : O(1)

Total Time: O(n)

Space: O(n)

But he wants an O(n) solution with O(1) extraspace. Anyone have any idea?

Upvotes: 4

Views: 2492

Answers (2)

MBo
MBo

Reputation: 80287

Make two index pointers - Left and Right, initialize both to the start of array (0). If a[Left] + k > a[Right], increment Right, else increment Left. Stop when equal

Upvotes: 8

Petar Ivanov
Petar Ivanov

Reputation: 93080

The idea is to use two pointers into the array say a and b. Originally they both point to the beginning (a=b=0).

If ar[a]+k < ar[b], then you advance a.

If ar[a]+k > ar[b], then you advance b.

If ar[a]+k == ar[b], then you have found a solution.

That's O(n) time and O(1) space.

Upvotes: 6

Related Questions