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

Posted in

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

Vinay Khatri
Last updated on September 21, 2022

    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:

    Leave a Comment on this Post

    0 Comments