Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Minimum Difference Element (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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 2 replies

Reading Progress

0%

Vote for new content