Tuesday, March 12, 2013

Different ways to find the magnitude pole of an array:

1) logic: bruteforce
    start from beginning of an array to end of an array and check all the before elements are <= the item and right elements are
> than it.

    O(n^2) Time complexity
    O(1) space complexity

2) logic: If any item is a magnitude pole of an array, then its position wont change after sorting 

   2.1) copy the original array into another array
   2.2) sort  it using o(n^2) insertion/bubble sort or o(n logn) merge sort.
   2.3) Check the original and sorted array  if any item is equal, return the index.
    if no match is found, return -1
  
   O (n log n) time complexity
   O (n) space complexity

   This approach may fail with below inputs:

            2 5 3 1 4
    ascending:  1 2 3 4 5

            2 1 3 5 4   
 

3) logic:If any item is a magnitude pole of an array, then  it will be the maximum and minimum of an array index.

   O(n) time complexity
   O(n) space complexity
  
 3.1) start from beginning and find max of array index[Extra array]
 3.2) start from end and find min of array index [change inplace of original array]
 3.3) Check the max and min array  if any item is equal, return the index.
    if no match is found, return -1
    
   
4) with simple code: o(n) time
                     o(1) space
  int magnitudePole(int a[])
   {
    int i_pole = 0;
    int i_max  = 0;
    bool have_pole = true;
    for (int i = 1; i < N; i++)
    {
        if (A[i] < A[i_pole])
        {
            have_pole = false;
        }
        if (A[i] > A[i_max])
        {
            i_max = i;
            if (!have_pole)
            {
                i_pole = i;
            }
            have_pole = true;
            cout <<endl<< " It has pole @" << i_pole;   
        }
    }
    if( have_pole)
    {
      // cout <<endl<< " It has pole @" << i_pole;   
       return i_pole;
    }
   
    return -1;
   }

5) o(n) time complexity
THis is also similar to max and min approach instead of comparing
min and max arrays, they are using BitSet class to do this job.


 import java.util.BitSet;
public static int magnitudePole(int[] A) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
BitSet bits1 = new BitSet(A.length);
BitSet bits2 = new BitSet(A.length);
for (int i = 0; i < A.length; ++i) {
if (A[i] >= max) {
bits1.set(i);
max = A[i];
}
}
for (int i = A.length - 1; i >= 0; --i) {
if (A[i] <= min) {
bits2.set(i);
min = A[i];
}
}
System.out.println(bits1.toString());
System.out.println(bits2.toString());
bits1.and(bits2);
return bits1.nextSetBit(0);
}

Labels:

1 Comments:

Blogger obsidianart said...

Please fix number 4
if (A[i] > A[i_max])
should be
if (A[i] >= A[i_max])

Failing array
[4,2,3,1,4,7,10,6,7]

7:09 AM  

Post a Comment

<< Home