Interesting Array

Last Updated on March 28, 2022 by Ria Pathak

Concepts used:

Two Pointers Technique

Difficulty level:

Medium

Problem statement(SIMPLIFIED):

Given an array A with N elements arranged in an ascending order, also given a number K. Check if their exist two indices such that sum of elements at those indices is equal to K. If Yes print those indices accordingly else print no answer.

NOTE: If there are multiple such pair (i, j), print max j value pair and if all j′s are equal print min i value pair.

See original problem statement here

For Example:

Input : 

N = 5 , K = 34
A = [12, 14, 16, 17, 20]

Output : 1 4

Explanation : elements at index 1 and 4 sum up to give 34 i.e. arr[1] + arr[4] = 34

Solving approach:

BRUTEFORCE METHOD:

1. Naive Solution would be to run two nested loops. Outer loop for picking each element one by one and inner loop for picking rest of the elements one by one.

2. Check for each index if their exists another index such that the values at both the indexes sum up to the required value, these indexes are our required solution.

3. Time Complexity of naive approach is O(N²).

EFFICIENT METHOD:

1. The idea is to use Two Pointers Technique, which is really an easy and effective technique typically used for searching pairs in a sorted array.

2. We take two pointers, one representing the first element and another representing the last element of the array. Then we add the values kept at both the pointers. If the sum is less than required value, we will shift left pointer to the right by 1 or if their sum is greater than the required value we will shift right pointer towards the left by 1, in order to get closer to the required value. We keep on shifting both the pointers till we get the required value or the required value is not present.

3. Time Complexity of this technique is O(n).

NOTE: This technique only works for Sorted Arrays.

Why are we moving left and right in the array?

As the given array is already sorted, lets say X is our current sum of first and last element. If we want a value less than X we can decrement our right pointer by 1 now right will point to an element that is less that the previous element. Similarly if we want a value greater than X, we can simply increment our left pointer by 1, now this will point to an element that is greater than the last element.

Illustration:

A[] = [12, 14, 16, 17, 20]
K = 30

i = 0
j = 4
A[i] + A[j] = 12 + 20 = 32
Since A[i] + A[j] > K, j--

i = 0 
j = 3
A[i] + A[j] = 12 + 17 = 29
Since A[i] + A[j] < K, i++

i = 1
j = 3 
A[i] + A[j] = 14 + 17 = 31
Since A[i] + A[j] > K, j--

i = 1
j = 2
A[i] + A[j] = 14 + 16 = 30
Since A[i] + A[j] = K
We found out pair and resultant indexes are (1, 2)

Solutions:

#include < stdio.h >

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;ik)
      j--;
    else 
      i++;
  }
  if(flag==0)
    printf("no answer\n");
 
  }
 
  return 0;
}

#include < bits/stdc++.h >
using namespace std;

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n;
    int arr[n];
    for(int i=0;i>arr[i];
    cin>>k;
    int i=0,j=n-1;
    int flag =0;
  while(ik)
      j--;
    else 
      i++;
  }
  if(flag==0)
    cout<<"no answer"<<"\n";

  }

  return 0;
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t!=0)
    {
      int n = sc.nextInt();
      int arr[] = new int[n];
      for(int i=0;ik)
        j--;
      else 
        i++;
    }
    if(flag==0)
      System.out.println("no answer");
    t--;
    }
  }
}

# your code goes heren, k = map(int,input().split())
arr = list(map(int,input().split()))
i, j = 0, n - 1
flag = 0
while i < j:
	if arr[i] + arr[j] == k:
		print(i, j)
		flag = 1
		break
	elif arr[i] + arr[j] > k:
		j -= 1
	else:
		i += 1

if flag == 0:
	print("no answer")

This article tried to discuss Two Pointers Technique. Hope this blog helps you understand and solve the problem. To practice more problems on you can check out MYCODE | Competitive Programming.