CODEWITHSUNDEEP
javaarraysalgorithmdata-structuresindexoutofboundsexception
Divyansh Purohit
Divyansh Purohit

Reputation: 61

Data Structure problem : Minimize the maximum difference between the heights, why is my solution not working

Here is the link to the problem : https://practice.geeksforgeeks.org/problems/minimize-the-heights3351/1#

Problem statement:Given an array arr[] denoting heights of N towers and a positive integer K, you have to modify the height of each tower either by increasing or decreasing them by K only once. After modifying, height should be a non-negative integer. Find out what could be the possible minimum difference of the height of shortest and longest towers after you have modified each tower.

My solution is passing basic test cases but when I submit ArraysIndexOutOfBound exception is thrown. I am using the sliding window methdod. Please help me find the bug. Thank you!

class Pair{
    private int index;
    private int value;
    Pair(int index, int value){
        this.index=index;
        this.value=value;
    }
   public int getIndex(){
       return this.index;
   }
   
   public int getValue(){
       return this.value;
   }
}

class Solution {
    int getMinDiff(int[] a, int n, int k) {
      ArrayList<Pair> possibleHeights =new ArrayList<Pair>();
      int [] visited = new int[n];
    //   for(int i=0;i<n;i++){
    //     System.out.println(a[i]-k);
    //   } 
      for(int i=0;i<n;i++){
          if((a[i]-k)>=0)
          possibleHeights.add(new Pair(i,a[i]-k));
          possibleHeights.add(new Pair(i,a[i]+k));
          visited[i]=0;
      } 
      
    //   for(int i=0;i<possibleHeights.size();i++){
    //       System.out.println(possibleHeights.get(i).getIndex()+"--"+possibleHeights.get(i).getValue());
    //   }
    //     System.out.println("---------");
      
      Collections.sort(possibleHeights,new Comparator<Pair>(){
          public int compare(Pair p1,Pair p2){
              return p1.getValue()-p2.getValue();
          }
      });
    //   for(int i=0;i<possibleHeights.size();i++){
    //       System.out.println(possibleHeights.get(i).getIndex()+"--"+possibleHeights.get(i).getValue());
    //   }
      
      int left=0,right=0,ele=0,size=possibleHeights.size();
      while(ele<n&&right<size&&left<size){
          if(visited[possibleHeights.get(right).getIndex()]==0)
          ele++;
          visited[possibleHeights.get(right).getIndex()]++;
          right++;
      }
      int ans = possibleHeights.get(right-1).getValue()- possibleHeights.get(left).getValue();
      while(right<size&&left<size){
          if(possibleHeights.get(left).getIndex()==1)
          ele--;
          visited[possibleHeights.get(left).getIndex()]--;
          left++;
            while(ele<n&&right<size&&left<size){
          if(visited[possibleHeights.get(right).getIndex()]==0)
          ele++;
          visited[possibleHeights.get(right).getIndex()]++;
          right++;
      }
      int temp=possibleHeights.get(right-1).getValue()- possibleHeights.get(left).getValue();
        if(ele==n)      
        ans=ans<temp?ans:temp;
        else 
        break;
      }
      return ans;
    }
}

Upvotes: 0

Views: 347

Answers (1)

user2711811
user2711811

Reputation:

This test case fails with the IndexOutOfBoundsException and your lack of indentation following conditionals (with no block statements) makes it difficult to help further...

N=5, a=[1,5,8,10,1] K=3

(No where does it say the input a[] should be assumed to be numerically sorted - although both their examples are sorted.)

Results in

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 8, Size: 8
    at java.util.ArrayList.rangeCheck(ArrayList.java:657)
    at java.util.ArrayList.get(ArrayList.java:433)
    at Main$Solution.getMinDiff(Main.java:84)
    at Main.main(Main.java:32)

(In my environment, line Main.java:84 is:

int temp=possibleHeights.get(right-1).getValue()- possibleHeights.get(left).getValue();

Your lack of indentation (with no block statements) is somewhat maddening and makes it difficult to understand your intent:

      if((a[i]-k)>=0)
      possibleHeights.add(new Pair(i,a[i]-k));
      possibleHeights.add(new Pair(i,a[i]+k));
      visited[i]=0;

If (a[i]-k)>=0 is false, did you intend to have only the one line (immediately following) executed?

I suggest coming up with a good set of test cases (lots of them) (and post with your problem) which includes edge cases (values at their limits).

Upvotes: 1

Related Questions