Greater than Neighbor

Last Updated on July 24, 2023 by Mayank Dham

In this article, we will be looking at how we can solve the problem Greater than neighbor, in which you are given an Array and you need to print all the indexes that have a value greater than its left and right neighbors.

PROBLEM STATEMENT(SIMPLIFIED):

Given an array A of N elements, your task is to print all those indexes that have values greater than its left and right neighbors. In case of extreme indexes like 0 and N-1, check with their single neighbor.

See original problem statement here

For Example:

SOLVING APPROACH:

The idea is to traverse the array from left and for each index, check if the value at it is greater than its neighbor. If Yes print its index. If no such index is found, simply print -1.

SOLUTIONS:

#include < stdio.h >

int main()
{
  int t; scanf("%d", &t);

  while(t--){
    int n; scanf("%d", &n);
    int arr[n];

    for(int i=0; i arr[i+1]){
                printf("%d ", i);
                flag = 1;
            }
        }

        else if(i == n-1){
            if(arr[i] > arr[i-1]){
                printf("%d ", i);
                flag = 1;
            }
        }
        else{
            if(arr[i] > arr[i-1] && arr[i] > arr[i+1]){
                printf("%d ", i);
                flag = 1;
            }
        }  
    }
    if(flag == 0)
      printf("-1");
    printf("\n");
  }

  return 0;
}

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

  int main()
  {
    int t; cin >> t;

    while(t--){
      int n; cin >> n;
      int arr[n];

      for(int i=0; i> arr[i];
      }

      int flag = 0;
      for(int i=0; i arr[i+1]){
              cout << i << " ";
              flag = 1;
            }
        }

        else if(i == n-1){
            if(arr[i] > arr[i-1]){
              cout << i << " ";
              flag = 1;
            }
        }

        else{
            if(arr[i] > arr[i-1] && arr[i] > arr[i+1]){
                cout << i << " ";
                flag = 1;
            }
        } 
      }

      if(flag == 0)
        cout << "-1";
      cout << endl;
    }

    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; i arr[i+1]){
              System.out.print(i + " ");
              flag = 1;
            }
          }

          else if(i == n-1){
            if(arr[i] > arr[i-1]){
              System.out.print(i + " ");
              flag = 1;
            }
          }
          else{
            if(arr[i] > arr[i-1] && arr[i] > arr[i+1]){
                System.out.print(i + " ");
                flag = 1;
            }
          }
        }
        if(flag == 0)
          System.out.print("-1");
        System.out.println();

        t--;
      }

    }
  }

# your code goes heren = int(input())
arr = list(map(int,input().split()))
flag = 0

for i in range(n):
	if i == 0:
		if arr[i] > arr[i + 1]:
			print(i, end = " ")
			flag = 1
	elif i == n - 1:
		if arr[i] > arr[i - 1]:
			print(i, end = " ")
			flag = 1
	else:
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			print(i, end = " ")
			flag = 1

if flag == 0:
	print(-1)

Space Complexity: O(N)
Space Complexity: O(1)

[forminator_quiz id="484"]

Conclusion
In this article, we explored how to solve the problem "Greater than Neighbor," where we are given an array and need to find and print all the indexes that have a value greater than both their left and right neighbors. The approach to solving the problem involved traversing the array from left to right and checking if the value at each index satisfied the condition. If a valid index is found, it is printed; otherwise, -1 is printed. The time complexity of the solution is O(N), where N is the number of elements in the array, making it an efficient solution for this problem. The space complexity is O(1), indicating that the solution uses a constant amount of memory regardless of the size of the input.

Frequently Asked Questions (FAQs)

Here are some of the most frequently asked questions related to the greater than neighbor problem.

Q1. What is the highest element in an array?
The highest element in an array is the element with the greatest value among all the elements present in the array.

Q2. What is the peak element in a list?
In a list or an array, a peak element is an element that is greater than or equal to its adjacent elements. It forms a local maximum, as it is larger than both its left and right neighbors.

Q3. What is the next greater element of an element?
The next greater element of an element refers to the element that appears immediately after it and has a value larger than the current element. It is relevant in the context of searching for the closest value.

Q4. What is a peak in data structure?
In data structures, a peak refers to a specific element in an array or list that satisfies a certain condition, usually being greater (or lesser) than its neighboring elements. Peaks can have various applications in data analysis and optimization algorithms.

Q5. What is the pivot element in an array?
In the context of sorting algorithms like Quick Sort, the pivot element in an array is a chosen element used to partition the array into two parts during each iteration. The elements smaller than the pivot are moved to its left, and the elements greater than the pivot are moved to its right, putting the pivot in its correct sorted position.