Adjacent Element Comparison

The adjacent element comparison involves comparing adjacent elements in an array or list and performing some operation based on the comparison result.

Some examples:

  • Find the number of adjacent pairs where the first element is larger than the second.
  • Replace adjacent duplicate elements with 0.
  • Remove adjacent duplicate letters from a string.

Some sample code:

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Count adjacent pairs where a[i] > a[i+1]
int count = 0;
for (int i = 0; i < a.length - 1; i++) {
  if (a[i] > a[i+1]) count++;
}

// Replace adjacent duplicates with 0
for (int i = 0; i < a.length - 1; i++) {
  if (a[i] == a[i+1]) {
    a[i] = a[i+1] = 0; 
  }
}

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Remove adjacent duplicate letters 
str = "Hello World"
result = ""
prev = None
for char in str:
  if char != prev:
    result += char
    prev = char

print(result) # "Helo Wrd"

The key steps are:

  • Iterate through array/list, accessing adjacent elements via loop index
  • Perform comparison or other ops on adjacent pairs
  • Update result array/list or counters

Time complexity is O(N) for array of size N. Allows solving problems requiring adjacent element analysis.

Adjacent Element Comparison is a simple technique where each element in a collection (such as an array or list) is compared with its immediate neighboring element. This method is used to identify specific properties, like sorting, finding local maxima or minima, or identifying consecutive elements that meet certain criteria.

The process involves iterating through the collection and comparing each element with its next neighbor. This leads to ( n - 1 ) comparisons for a collection of ( n ) elements.

Solution

Below are the examples of adjacent element comparison in Java, C++, and Python. These examples demonstrate finding whether the given array is sorted in ascending order by using adjacent element comparison.

Java

1
2
3
4
5
6
7
8

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 2; i++) {
        if (arr[i] > arr[i + 1]) {
            return false; // If current element is greater than next, array is not sorted
        }
    }
    return true; // Array is sorted
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <iostream>

bool isSorted(int arr[], int size) {
    for (int i = 0; i < size - 2; i++) {
        if (arr[i] > arr[i + 1]) {
            return false; // If current element is greater than next, array is not sorted
        }
    }
    return true; // Array is sorted
}

Python

1
2
3
4
5

def is_sorted(arr):
    for i in range(len(arr) - 2):
        if arr[i] > arr[i + 1]:
            return False # If current element is greater than next, array is not sorted
    return True # Array is sorted

Another alternative is to compare the current element with the preceding element. Start the index from 1 to array length - 1.

Key Takeaways

  • Adjacent Element Comparison involves comparing an element with its immediate neighbor in a collection.
  • It is useful for various purposes, including checking if a collection is sorted or finding local patterns.
  • The code examples demonstrate how to use adjacent element comparison to check if an array is sorted in ascending order.
  • This technique is efficient and easy to implement, making it a valuable tool in various algorithms and problem-solving scenarios.

Traversing an array with two index variables pointing to adjacent elements can be useful for comparing pairs of elements in the array. This technique is often employed in algorithms that require you to find relations between adjacent elements, like finding if the array is sorted in ascending order.

Traverse an Array with Two Index Variables Pointing to Adjacent Elements

Traversing an array using two index variables pointing to adjacent elements is a common technique. This approach is often used to compare neighboring elements or find patterns within an array. Two index variables, typically i and j, are initialized such that j = i + 1. The loop then iterates over the array, and operations are performed on array[i] and array[j].

Example Code

Java
1
2
3
4
5
6
7
8
9

public class Main {
  public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    
    for (int i = 0, j = 1; j < array.length; i++, j++) {
      System.out.println("Adjacent elements: " + array[i] + ", " + array[j]);
    }
  }
}
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <iostream>
using namespace std;

int main() {
  int array[] = {1, 2, 3, 4, 5};
  int length = sizeof(array) / sizeof(array[0]);
  
  for (int i = 0, j = 1; j < length; i++, j++) {
    cout << "Adjacent elements: " << array[i] << ", " << array[j] << endl;
  }
  
  return 0;
}
Python
1
2
3
4
5

array = [1, 2, 3, 4, 5]

for i in range(len(array) - 1):
    j = i + 1
    print(f"Adjacent elements: {array[i]}, {array[j]}")
  • The loop iterates through the array using only one index variable, i.
  • A second index, j, is set as i + 1 within the loop.
  • The elements at these indices are then accessed and printed.

Key Takeaways

  • Two index variables (i and j) are initialized such that j = i + 1.
  • The loop iterates over the array using these index variables.
  • This allows for easy comparison or manipulation of adjacent elements in the array.