Find the minimum difference between the index of two given elements present in an array

Problem

Given two integers, find the minimum difference between their index in a given array in linear time and a single traversal of the array.

Sample Input

[1, 2, 3, 4]
X=2, Y=4

Sample Output

2

Approach

We need to handle these two cases in this problem:

1. If the current element is X , then find the absolute difference between current index and last occurrence of Y and update the answer if needed.
2. If the current element is Y , then find the absolute difference between current index and last occurrence of X and update the answer if needed.

C++ Programming

#include<bits/stdc++.h>
using namespace std;
int solve(int arr[], int n, int x, int y)
{
    int indexX = n, indexY = n;
    int ans = INT_MAX;
 
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == x)
    
        {

            indexX = i;
 
            if (indexY != n) {
                ans = min(ans, abs(indexX - indexY));
            }
        }
 
        if (arr[i] == y)
        
        {
        
            indexY = i;
 
            if (indexX != n) {
                ans = min(ans, abs(indexX - indexY));
            }
        }
    }
 
    return ans;
}
 
int main(void)
{
    int arr[] = { 1, 2, 3, 4};
    int x = 2, y = 4;
 
    int n = sizeof(arr) / sizeof(arr[0]);
    int diff = solve(arr, n, x, y);
    if (diff != INT_MAX) {
        cout<<diff;
    }
    else {
        cout<<"Invalid input";
    }
 
    return 0;
}

Output

2

C Programming

#include <stdio.h>
#include <limits.h>
#include <math.h>
 
int min (int x, int y) {
    return (x < y) ? x : y;
}
 

int solve(int arr[], int n, int x, int y)
{
    int indexX = n, indexY = n;
    int ans = 10000000;  
 
    for (int i = 0; i < n; i++)
    {

        if (arr[i] == x)
        {

            indexX = i;
 
            if (indexY != n) {
                ans = min(ans, abs(indexX - indexY));
            }
        }
 
        if (arr[i] == y)
        {
            indexY = i;
 
            if (indexX != n) {
                ans = min(ans, abs(indexX - indexY));
            }
        }
    }
 
    return ans;
}
 
int main(void)
{
    int arr[] = { 1, 2, 3, 4 };
    int x = 2, y = 4;
 
    int n = sizeof(arr) / sizeof(arr[0]);
    int diff = solve(arr, n, x, y);
 
    if (diff != 10000000) {
        printf("%d", diff);
    }
    else {
        printf("Invalid input");
    }
 
    return 0;
}

Output

2

Python Programming

def solve(arr, x, y):
    indexX = indexY = len(arr)
    ans = 10000000
 
    for i in range(len(arr)):
 
        if arr[i] == x:

            indexX = i
 
            if indexY != len(arr):
                ans = min(ans, abs(indexX - indexY))
 
        if arr[i] == y:
 
            indexY = i
 
            if indexX != len(arr):
                ans = min(ans, abs(indexX - indexY))
 
    return ans
 
arr = [1, 2, 3, 4]
x = 2
y = 4
 
diff = solve(arr, x, y)
 
if diff != 10000000:
    print(diff)
else:
    print("Invalid input")

Output

2

People are also reading:

• Longest Increasing Subsequence using Dynamic Programming
• Convert a Binary Tree to Doubly Linked List
• Merge Sort for Linked Lists
• Check if a subarray with 0 sum exists or not
• Find a Pair with the Given Sum in an Array
• Move all zeros present in an array to the end
• Rod Cutting Problem
• Sort binary array in linear time
• Program to Rotate an Array
• Subarray with Sum k