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.
Comments
Post a Comment