Unknown_712's blog

TWO POINTER ALGORITHM
By Unknown_712, history, 4 years ago, In English

THIS ALGORITHM IS VERY USEFUL.IF WE SEE TYPES OF PROBLEM LIKE FIND OF 2 NUMBERS FROM ARRAY WHOSE SUM IS EQUAL TO X.IF WE DON'T KNOW WHAT IS TWO POINTER ALGORITHM THEN THIS PROBLEM CAN BE SOLVED BY O(n^2) (ONE FOR LOOP INSIDE THE ANOTHER)where n is no. of element in array by two pointer algorithm we can solve such type of problem in o(n) for sorted array and o(nlogn) for unsorted array. if array is not sorted then we have to first sort the array because this algorithm is useful only for sorted arrays in this technique we use two pointer first one is pointing at the starting index and second one is at last index then we find sum of values at these pointers and we will compare this given sum if sum of values is less than given sum we will increment first pointer by 1 if our sum is greater than given sum then we will decrement the last pointer by 1; if we found our sum is equals to given sum then we will return iterate this while loop until(first pointer<last pointer)

BY THIS ALGORITHM WE CAN SOLVE SUCH TYPE OF PROBLEMS IN LESS TIME COMPLEXICITY AS WELL AS IN EASY WAY; FOR EACH BEGINNER ONE SHOULD N KNOW ABOUT THIS ALGORITHM

  • Vote: I like it
  • -37
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Hello sir. I dont understand how you get o(n) complexity wouldn't it be O(n)? I am declining in cp(see my last delta) so I might need further elaboration.

Other than that I think you should add more newlines (<br> or 2 newlines) to make it more accessible for beginners.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    HII, IF ARRAY IS SORTED THEN TIME COMPLEXICITY WOULD BE O(N) IF ARRAY IS NOR SORT THEN FIRST WE HAVE TO SORT THE ARRAY SO TIME CIMPLEXICITY WOULD BE O(NLOGN) IN UNSORTED ARRAY BY THIS ALGORITHM WE CAN USE SOLVE SOME SPECIFIC TYPES OF PROBLEM WITH LESS COMPLEXICITY. PROBLEMS LIKE IN AN SORTED ARRAY FIND 3 DIFFERENT NUMBERS FROM THE ARRAY WHOSE SUM IS X IF WE GO BRUTE FROCE SOLUTION TIME COMPLEXICITY WOULD BE O(N^3) BUT USE OF THIS ALGORITHM WE CAN SOLVE THIS PROBLEM IN O(N^2) SO THE MAIN USE OF THIS ALGORITHM IS TO REDUCE TIME COMPLEXICITY FOR SUCH TYPES OF PROBLEM FROM ABOVE EXAMPLE WE CAN SEE THAT WE REDUCED THE TIME COMPLEXICITY FROM O(N^3) TO O(N^2) IT IS VERY EASY TO APPLY

    include

    using namespace std;

    // Two pointer technique based solution to find // if there is a pair in A[0..N-1] with a given sum. int isPairSum(int A[], int N, int X) { // represents first pointer int i = 0;

    // represents second pointer
int j = N - 1;

while (i < j) {

    // If we find a pair
    if (A[i] + A[j] == X)
       return 1;

    // If sum of elements at current
    // pointers is less, we move towards
    // higher values by doing i++
    else if (A[i] + A[j] < X)
       i++;

    // If sum of elements at current
    // pointers is more, we move towards
    // lower values by doing j--
    else
       j--;
}
return 0;

    }

    // Driver code int main() { // array declaration int arr[] = { 3, 5, 9, 2, 8, 10, 11 };

    // value to search
int val = 17;

// size of the array
int arrSize = *(&arr + 1) - arr;

// Function call
cout << (bool)isPairSum(arr, arrSize, val);

return 0;

    } BY THIS EXAMPLE YOUR ALL WILL BE SORT OUT THANKS FOR SUGGESTION DUDE FROM, NEXT ONWARDS BLOG I WILL ELOBORATE THESE IMPORTANT ALGORITHM IN DETAIL

    → Reply