Minimize Travel Distance to Collect K Objects on X-Axis

N objects are placed on X-axis, and coordinates are given. Starting your journey with coordinate 0, find minimum distance you need to travel to collect K objects (If multiple objects are placed on same position, you may collect some or all of them).

Examples:

Input: arr[] = {10, -10, -30, 20, 50},  K = 3
Output: 40
Explanation: 
Start with 0 (initial position) journey will be 0 --> (-10) --> 10 --> 20 .
Sum of distance is |-10-0| + |10-(-10)| + |20-10| = 40, which is minimum possible.

Input: arr[] = {4, -3, 5},  K = 2
Output: 5
Explanation: 
Start with 0 (initial position) journey will be 0 --> 4 --> 5 .
Sum of distance is |4-0|+ |5-4| = 5, which is minimum possible.

Recommended: Why Learn C++?

Approach:
Here are some observations and steps to solve given problem

Observations:-

If two objects with coordinates at x₁ and x₂ are collected, both from positive side (or both from negative side) then total distance will be max(|x₁|, |x₂|), if current position is 0.
Switching direction (from negative to positive Or vice versa) more than 1 time, will add some additional distance to answer.

Solution:-

Sort all the points in increasing order of coordinates.
Select all subarrays of length K, and for each subarray optimal total distance will be as :-
- If all the coordinates are negative, leftmost coordinate denotes total distance.
- If all the coordinates are positive, rightmost coordinate denotes total distance.
- If subarray contains both negative and positive, then there are 2 ways – select all negative first and then switch to positive Or vice versa.
Minimum distance among all these subarrays, is our optimal answer.

Below is the implementation of above approach:

#include <bits/stdc++.h>

using namespace std;

int minDistance(int arr[], int N, int K) {
  if (N < K)
    return -1;

  // sort the coordinates
  sort(arr, arr + N);
  int ans = 1e9;

  // select subarray of length K, starting at index i
  for (int i = 0; i < N - K + 1; i++) {
    int left = arr[i];
    int right = arr[i + K - 1];

    if (right <= 0) {
      // both ends are negative side
      left = abs(left);
      ans = min(ans, left);
    } else if (left >= 0) {
      // both ends are positive side
      ans = min(ans, right);
    } else {
      left = abs(left);

      // first left and then right
      ans = min(ans, left + left + right);

      // first right and then left
      ans = min(ans, right + right + left);
    }
  }

  return ans;
}

// Driver code
int main() {
  int N = 5;
  int arr[] = { 10, -10, -30, 20, 50 };
  int K = 3;

  cout << minDistance(arr, N, K);

  return 0;
}

Output:

Time Complexity: O(N logN)
Space Complexity: O(N)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.