Minimum Absolute Difference - C++ Solution

1. Introduction

This blog post discusses a problem that involves finding the minimum absolute difference between indices of two specific elements in an integer array. The challenge is to do this in a single traversal of the array, making it a test of efficient array processing.

Problem

Given an integer array nums and two integers x and y present in it, the objective is to find the minimum absolute difference between the indices of x and y.

2. Solution Steps

1. Initialize variables to store the last indices of x and y, and set the minimum difference to a large value.

2. Traverse the array once.

3. Update the last indices of x and y when encountered.

4. Calculate the absolute difference of the current indices of x and y when both have been encountered at least once.

5. Update the minimum difference accordingly.

6. Return the minimum difference.

3. Code Program

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int minAbsoluteDifference(const vector<int>& nums, int x, int y) {
    int lastX = -1, lastY = -1, minDiff = INT_MAX;

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == x) {
            lastX = i;
            if (lastY != -1) {
                minDiff = min(minDiff, abs(lastX - lastY));
            }
        } else if (nums[i] == y) {
            lastY = i;
            if (lastX != -1) {
                minDiff = min(minDiff, abs(lastX - lastY));
            }
        }
    }

    return (minDiff == INT_MAX) ? 0 : minDiff;
}

int main() {
    vector<int> nums = {1, 3, 5, 4, 8, 2, 4, 3, 6, 5};
    int x = 3, y = 2;
    cout << "Minimum Absolute Difference: " << minAbsoluteDifference(nums, x, y) << endl;
    return 0;
}

Output:

Minimum Absolute Difference: 2

Explanation:

The function minAbsoluteDifference calculates the minimum absolute difference between the indices of elements x and y in the array. It keeps track of the last positions where x and y were encountered and updates the minimum difference each time both x and y have been seen. For the input array [1, 3, 5, 4, 8, 2, 4, 3, 6, 5] with x = 3 and y = 2, the minimum absolute difference between their indices is 2, corresponding to the positions of 3 at index 1 and 7, and 2 at index 5.