2 Replies - 251 Views - Last Post: 13 January 2020 - 12:58 PM Rate Topic: -----

#1 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 18
  • View blog
  • Posts: 301
  • Joined: 25-May 16

Better optimize smallest difference

Posted 13 January 2020 - 10:29 AM

Hi everyone, I'm having a little fun with trying to come up with algorithms that have a better time/space complexity.

I came across this one problem where I am given two different arrays (can be in any order and any positive/negative integer is allowed) and I must find the smallest difference between the two arrays.

So if the difference between the first array and second array are 0, that would be the smallest difference since that means they are equal to each other.

To make things simpler, we will assume that there is only one pair that has the smallest difference. When you find it, you then output the pair in an array with those 2 values.

The solution below is my solution and I was wondering if there was a more efficient or better way to do this.

Worst case scenario, my solution is O(n2) time complexity and O(1) space

What do you all think?

using System;
public class Program {
	public static int[] SmallestDifference(int[] arrayOne, int[] arrayTwo) {
		// Write your code here.
		int smallest = Int32.MaxValue;
		int[] smallestDiff = new int[] { 0, 0 };
		
		for(int i = 0; i < arrayOne.Length; i++)
		{
			for(int j = 0; j < arrayTwo.Length; j++)
			{
				if(Math.Abs(arrayOne[i] - arrayTwo[j]) < smallest)
				{
					smallest = Math.Abs(arrayOne[i] - arrayTwo[j]);
					smallestDiff[0] = arrayOne[i];
					smallestDiff[1] = arrayTwo[j];
				}
			}
		}
		
		return smallestDiff;
	}
}



Is This A Good Question/Topic? 1
  • +

Replies To: Better optimize smallest difference

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7244
  • View blog
  • Posts: 24,556
  • Joined: 05-May 12

Re: Better optimize smallest difference

Posted 13 January 2020 - 12:26 PM

Sort first and second arrays separately. Do a merge sort keeping track of the differences between first and second sorted array elements.
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7244
  • View blog
  • Posts: 24,556
  • Joined: 05-May 12

Re: Better optimize smallest difference

Posted 13 January 2020 - 12:58 PM

On thinking some more, just sort the first array. Then using values from the second array, do a pretend insertion sort or a binary search on the first sorted array. Compute differences between the neighbors of where the value would go.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1