Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Minimum Difference Element (medium)

Problem Statement

Given an array of numbers sorted in ascending order, find the element in the array that has the minimum difference with the given key.

Example 1:

Input: [4, 6, 10], key = 7
Output: 6
Explanation: '6' is closer to the key '7' than any other number in the array.

Example 2:

Input: [4, 6, 10], key = 4
Output: 4

Example 3:

Input: [1, 3, 8, 10, 15], key = 12
Output: 10

Example 4:

Input: [4, 6, 10], key = 17
Output: 10

Constraints:

  • 1 <= arr.length <= 10<sup>4</sup>
  • -10<sup>4</sup> <= arr[i], key <= 10<sup>4</sup>

.....

.....

.....

Like the course? Get enrolled and start learning!
Joshua Cheng

Joshua Cheng

· 7 days ago

I was able to write a "find the floor solution" which is wrong but still passes all of the tests. You are missing a test case like this:

[1, 3, 8, 10, 15]

14

which should return 15, but the below returns 10

class Solution: def searchMinDiffElement(self, arr, key): l, r = 0, len(arr) - 1 while l <= r: mid = (l + r) // 2 if arr[mid] > key: r = mid - 1 elif arr[mid] < key: l = mid + 1 else: return arr[mid]

return arr[0] if r < 0 else arr[r]

Gustavo Alves

Gustavo Alves

· 10 months ago

My solution gives this error when running submit:

RuntimeException 0.071 s

Runtime error: Cannot read properties of undefined (reading 'length')

Your Input[10, 20, 30, 40, 50] 35 Output undefined Expected 30

But when i run it manually it passes just fine.

Show 1 reply
P

Pete Stenger

· 2 years ago

class Solution:
  def searchMinDiffElement(self, arr, key):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if arr[mid] == key:
        return arr[mid]
      elif arr[mid] < key:
        lo = mid + 1
      else:
        hi = mid - 1
    
    # lo holds idx right after
    after = math.inf if lo >= len(arr) else arr[lo]
    # hi holds idx right before
    before = -math.inf if hi < 0 else arr[hi]
    
    if after - key < key - before:
      return after
    else:
      return before
Show 1 reply
L

lejafilip

· 2 years ago

  static int searchMinDiffElement(const vector<int>& arr, int key) {
    if(arr[arr.size() - 1] <= key)
      return arr[arr.size() - 1];
    else if(arr[0] >= key)
      return arr[0];

    std::pair<int, int> minDiff{std::numeric_limits<int>::max(), -1};
    auto start = 0;
    auto end = arr.size() - 1;
    
    while(start <= end)
    {
      auto mid = (start + end) / 2;

      if(arr[mid] == key)
        return key;
      else if(arr[mid] > key)
      {
        auto diff = std::abs(arr[mid] - key);
        if(diff < minDiff.first)
        {
          minDiff.first = diff;
          minDiff.second = arr[mid];
        }
        end = mid - 1;
      }
      else
      {
        auto diff = std::abs(arr[mid] - key);
        if(diff < minDiff.first)
        {
          minDi
Show 1 reply
L

Learner

· 5 years ago

Why do we need to use this specific sequence while finding the diff: if ((arr[start] - key) < (key - arr[end])) instead of the absolute value?

Can you please provide an example why absolute won't work?

Show 3 replies

Reading Progress

0%

Vote for new content