# A magnitude pole of an array problem

• 06-28-2012, 04:15 PM
Java2012
A magnitude pole of an array problem
Hello all;

The problem is to find the magnitude pole of an array:

"A magnitude pole of an array A consisting of N integers is an index K such that all elements with smaller indexes have values lower or equal to A[K] and all elements with greater indexes have values greater or equal to A[K], i.e.
For example:
5 is a magnitude pole of array A such that
A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9."

I need to figure out why this solution does not work:

Code:

``` public int magnitudePole(int[] A)   {     boolean foundLeft = true;         boolean foundRight = true;           for(int i = 0; i < A.length; i++)     {               for(int j = i - 1; j >= 0; j--)         {             if((A[i] - A[j]) < 0 )             {               foundLeft = false;                 break;             }             else             {               foundLeft = true;             }                   }                   for(int j = i + 1; j < A.length && foundLeft; j++)         {              if((A[j] - A[i]) < 0)             {                                foundRight = false;                                 break;                           }         }                  if(foundLeft && foundRight)         {             return i;                                 }             }       return -1;   }```

• 06-28-2012, 04:24 PM
KevinWorkman
Re: A magnitude pole of an array problem
How doesn't it work? What do you expect it to do? What does it do instead? You need to step through this with a debugger, or at the very least add some print statements, until you understand exactly what the program is doing.
• 06-28-2012, 04:37 PM
Java2012
Re: A magnitude pole of an array problem
Thank you for your help. With this example :

A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9."

It should give 5 , but it gives -1.

I went through every element on paper and it must work, I printed some values , but it does not help much.

Any help?
• 06-28-2012, 06:13 PM
KevinWorkman
Re: A magnitude pole of an array problem
Like I said, you'll have to step through this with a debugger, or at least add more print statements, until you figure out what's going on.
• 06-28-2012, 07:18 PM
Norm
Re: A magnitude pole of an array problem
It would help us to understand what the code is trying to do if you added comments to it describing what each part of the code is doing.
• 06-29-2012, 08:47 AM
Ksharp
Re: A magnitude pole of an array problem
Your code looks good.But you need to check it more ,especial for your logic.

Code:

```     public class x{       public static void main(String [] args)  {     int[] A={4,2,2,3,1,4,7,8,6,9};     boolean foundLeft ;     boolean foundRight ;     boolean found=false;     for(int i=1;i< A.length-1;i++) {     foundLeft = true;     foundRight = true;       for(int j=0;j<i;j++){                           if (A[j] > A[i]) foundLeft=false;                           }       for(int k=i+1;k<A.length;k++){                           if (A[i] > A[k]) foundRight=false;                           }     if (foundLeft && foundRight)  {System.out.println("Found it: " + i);found=true;}                                     }     if ( ! found ) System.out.println("Not Found.");           }   }```

Ksharp
• 06-29-2012, 08:56 AM
Java2012
Re: A magnitude pole of an array problem
Well I used your two advices printing statements, and checking every part. The problem in the code was, it should reset foundRight to true in the end of the main loop. So the code after the correction:

Code:

``` public  int magnitudePole(int[] A)   {     boolean foundLeft = true;         boolean foundRight = true;         //loop over each element and break the loop when you find the correct answer         for(int i = 0; i < A.length; i++)     {          //check all the left elements of the current element         for(int j = i - 1; j >= 0; j--)         {             if((A[i] - A[j]) < 0 )             {               foundLeft = false;                               break;             }             else             {                                               foundLeft = true;             }                   }           //if the all the left elements less than the current one check all the right elements of the current element                 for(int j = i + 1; j < A.length && foundLeft; j++)         {              if((A[j] - A[i]) < 0)             {                                foundRight = false;                                 break;                           }         }             //if all the left elements less than the current element       //and if all the right elements bigger than the current element     // return the index of the current element         if(foundLeft && foundRight)         {             return i;                                 } //the killing mistake was  foundRight should be reset to true  //and this was what made the code give the wrong answer even though the method is correct            foundRight = true;     }       return -1;     }```

Ok! thank you guys for your help.

Done!
• 04-21-2013, 12:07 PM
shukla2009
Re: A magnitude pole of an array problem Solution with O(n) time complexity
public int magnitudePole2(int[] A) {

int[] max = new int[A.length];
int[] min = new int[A.length];
int mx = Integer.MIN_VALUE;
int mn = Integer.MAX_VALUE;
for (int i = 0; i < A.length; i++) {
if (A[i] > mx)
mx = A[i];
max[i] = mx;
}
min[A.length - 1] = mn;
for (int i = A.length - 1; i > 0; i--) {
if (A[i] < mn)
mn = A[i];
min[i - 1] = mn;
}
for (int i = 0; i < A.length; i++) {
if (A[i] >= max[i] && A[i] < min[i])
return i;

}
return -1;
}
• 04-21-2013, 01:00 PM
JosAH
Re: A magnitude pole of an array problem
The OP already found a solution more than a year ago; I'm closing this thread.

kind regards,

Jos