old_contents: # Time:  O(nlogn + nlogw), n = len(nums), w = max(nums)-min(nums)
  # Space: O(1)
  
  # Given an integer array, return the k-th smallest distance among all the pairs.
  # The distance of a pair (A, B) is defined as the absolute difference between A and B.
  #
  # Example 1:
  # Input:
  # nums = [1,3,1]
  # k = 1
  # Output: 0 
  # Explanation:
  # Here are all the pairs:
  # (1,3) -> 2
  # (1,1) -> 0
  # (3,1) -> 2
  # Then the 1st smallest distance pair is (1,1), and its distance is 0.
  #
  # Note:
  # 2 <= len(nums) <= 10000.
  # 0 <= nums[i] < 1000000.
  # 1 <= k <= len(nums) * (len(nums) - 1) / 2.
  
  # Binary search with sliding window solution
  class Solution(object):
      def smallestDistancePair(self, nums, k):
          """
          :type nums: List[int]
          :type k: int
          :rtype: int
          """
          # Sliding window solution
          def possible(guess, nums):
              count, left = 0, 0
              for right, num in enumerate(nums):
                  while num-nums[left] > guess:
                      left += 1
                  count += right-left
              return count >= k
  
          nums.sort()
          left, right = 0, nums[-1]-nums[0]+1
          while left < right:
              mid = left + (right-left)/2
              if possible(mid, nums):
                  right = mid
              else:
                  left = mid+1
          return left
  
new_contents: # Time:  O(nlogn + nlogw), n = len(nums), w = max(nums)-min(nums)
  # Space: O(1)
  
  # Given an integer array, return the k-th smallest distance among all the pairs.
  # The distance of a pair (A, B) is defined as the absolute difference between A and B.
  #
  # Example 1:
  # Input:
  # nums = [1,3,1]
  # k = 1
  # Output: 0 
  # Explanation:
  # Here are all the pairs:
  # (1,3) -> 2
  # (1,1) -> 0
  # (3,1) -> 2
  # Then the 1st smallest distance pair is (1,1), and its distance is 0.
  #
  # Note:
  # 2 <= len(nums) <= 10000.
  # 0 <= nums[i] < 1000000.
  # 1 <= k <= len(nums) * (len(nums) - 1) / 2.
  
  # Binary search with sliding window solution
  class Solution(object):
      def smallestDistancePair(self, nums, k):
          """
          :type nums: List[int]
          :type k: int
          :rtype: int
          """
          # Sliding window solution
          def possible(guess, nums, k):
              count, left = 0, 0
              for right, num in enumerate(nums):
                  while num-nums[left] > guess:
                      left += 1
                  count += right-left
              return count >= k
  
          nums.sort()
          left, right = 0, nums[-1]-nums[0]+1
          while left < right:
              mid = left + (right-left)/2
              if possible(mid, nums, k):
                  right = mid
              else:
                  left = mid+1
          return left
  
subject: Update find-k-th-smallest-pair-distance.py