Approach:

- Iterate over an arr and overwrite each element by arr[i] = arr[i]+i
- Used min heap data structure with bound 2 so as to get max pair of element(Time complexity of inserting element in heap isO(logn)[worst case] ,similarly worst case time complexity is O(logn) best case isO(1))
- linear search to find respective index number of max pair
- computed ans using arr[max_index1]+arr[max_index2]-2*max_index2;
- Subtracted 2*max_index2; as we have to find arr[i]+arr[j]+i-j;

Complexity:

- Time Complexity: O(n) Linear time complexity
- Space complexity : O(2) ------ as heap is bounded with 2 which is constant

Code:

package com.desi.qna;
import java.util.Arrays;
import java.util.PriorityQueue;
public class ArraySum_ij {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {4,6,12,18,333,322};
get_sum_i_j(arr,arr.length);
}
private static void get_sum_i_j(int[] arr, int length) {
int i;
int max_index1 = 0,max_index2=0,ele1,ele2;
PriorityQueue<Integer> min_heap = new PriorityQueue<Integer>();
for(i=0;i<length;i++) {
arr[i]+=i;
min_heap.add(arr[i]);
if(min_heap.size()>2) {
min_heap.poll();
}
}
ele1 = min_heap.poll();
ele2 = min_heap.poll();
max_index1 = linearSearch(arr, ele1,0,length);
max_index2 = linearSearch(arr, ele2,0,length);
int ans = arr[max_index1]+arr[max_index2]-2*max_index2; //j is first added and then subtracted
System.out.println("arr["+max_index1+"] = "+(arr[max_index1]-max_index1)+" arr["+max_index2+"] = "+(arr[max_index2]-max_index2)+" i = "+max_index1+" j= "+max_index2);
System.out.println("ans = "+ans);
}
private static int linearSearch(int[] arr, int ele, int i, int length) {
// TODO Auto-generated method stub
for(i=0;i<length;i++) {
if(arr[i] == ele) {
return i;
}
}
return 0;
}
}