Minimum Difference Between Largest and Smallest Value in Three Moves

summary

• Find the minimum difference between the largest and smallest value of an integer array after performing at most three moves.

approach

• This solution uses a depth-first search (DFS) approach to try all possible moves and find the minimum difference
• The DFS function recursively tries different moves and updates the minimum difference
• The main function first sorts the array and then calls the DFS function with the initial minimum and maximum values.

complexity

• O(n * 4^3) where n is the number of elements in the array

explain

• The solution starts by sorting the input array
• Then, it uses a DFS function to try all possible moves
• The DFS function takes the current array, the current depth (which represents the number of moves made so far), the left and right indices of the current subarray
• If the current depth is 3, it means we have made 3 moves, so it returns the difference between the maximum and minimum values in the current subarray
• Otherwise, it recursively tries two possible moves: moving the left element to the right and moving the right element to the left
• The minimum difference found by these two recursive calls is returned
• The main function calls the DFS function with the initial minimum and maximum values and returns the result.

Solution Code:

int abs(int x){
    return x < 0 ? -x : x;
}
class Solution {
public:
    int dfs(vector&nums, int depth, int l, int r){
        if (depth == 3){
            return nums[r] - nums[l];
        }
        int res = dfs(nums, depth+1, l+1, r);
        res = min(res, dfs(nums, depth+1, l, r-1));
        return res;
    }
    int minDifference(vector& nums) {
        if (nums.size() <= 3) return 0;
        sort(nums.begin(), nums.end());
        int l = 0;
        int r = nums.size() - 1;
        return dfs(nums, 0, l, r);
    }
};