# 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}. `

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

and we see from figure 1 the answer match.

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.