Finding Differences in an Array

This week, we will focus on finding a difference within an array. The question is given an array with a number k, find all the pairs such that the difference between them is k. More specifically, given the values

arr = [0, -1, -2, 2, 1], k = 1

find the pairs that will give a difference of 1. A brute-force way to do this is create a nested loop and test if the difference between two numbers equal k

function findPairsWithGivenDifference(arr, k) {
  var sum = []
  for(var x = 0; x < arr.length; x++){
    for(var y = 0; y < arr.length; y++){
      if(arr[y] - arr[x] === k){
        sum.push([arr[y], arr[x]])
      }
    }
  }
  return sum
}. 

The expected answer is

output: [[1, 0], [0, -1], [-1, -2], [2, 1]]

and we see from figure 1 the answer match.

Fig. 1: Answer for arr = [0, -1, -2, 2, 1], k = 1.

The brute force works, but it is a bit slower because this is a nested loop, so for this case, the big O notation for this is O(n²). So let’s try to do it in O(n).

The question is: how do we do this problem so that we do not have a nested loop? The answer is use an object. We first declare the object and then we use a for loop to declare objects inside the object

var output = []
 var obj = {}
  
 for(var x = 0; x < arr.length; x++){       
   obj[arr[x] - k] = arr[x] 
 }. 

The next thing we want to do is check if the object has a property. What that means is given an object

var obj = {a: 1, b: 2, c: 3}, 

the property exists in the object if

obj.hasOwnProperty(property) === true. 

If we substitute property for a, b, or c, we will get true; if we use d, we receive false. The code is

for(var y = 0; y < arr.length; y++){
    if(obj.hasOwnProperty(arr[y]) === true){
      output.push([obj[arr[y]], arr[y]])
    }
  }
 return output

Full code is

function findPairsWithGivenDifference(arr, k) {

  var output = []
  var obj = {}
  
  for(var x = 0; x < arr.length; x++){       
    obj[arr[x] - k] = arr[x] 
  }
  
  for(var y = 0; y < arr.length; y++){
    if(obj.hasOwnProperty(arr[y]) === true){
      output.push([obj[arr[y]], arr[y]])
    }
  }
  return output
}

Because we used one for loop, our big O is O(n). We also get the same answer with this method too.

Fig. 2: Answer using objects.

I am interested in other methods or faster ways to solve this. Please let me know.