Traverse Forward and Backward

Concept Description

A single for loop can utilize two index variables, i and j, to traverse an array from both ends simultaneously. The index i starts at the beginning and moves forward, while j starts at the end and moves backward. This technique is useful when you want to compare or modify elements from both ends of an array in a single pass.

Example Code

Java

1
2
3
4
5
6
7
8

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        for(int i = 0, j = arr.length - 1; i <= j; i++, j--) {
            System.out.println("Forward: " + arr[i] + ", Backward: " + arr[j]);
        }
    }
}

C++

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

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    for(int i = 0, j = n - 1; i <= j; i++, j--) {
        cout << "Forward: " << arr[i] << ", Backward: " << arr[j] << endl;
    }

    return 0;
}

Python

1
2
3
4
5
6
7

arr = [1, 2, 3, 4, 5]
n = len(arr)
for i in range(n//2 + 1):
    j = n - 1 - i
    print(f"Forward: {arr[i]}, Backward: {arr[j]}")
    if i >= j:
        break

Key Takeaways

  • A single for loop can house two index variables i and j.
  • i starts at 0 and moves toward the center of the array.
  • j starts at the last index and moves toward the center.
  • Loop breaks when i is greater than or equal to j.

Palindrome Check

Using a single for loop with two index variables i and j to traverse a string forward and backward is an effective way to check for palindromes.

How it Works

  1. Initialize i to the start of the string (0) and j to the end of the string (length - 1).
  2. Compare the characters at i and j.
    • If they’re different, the string is not a palindrome.
    • If they’re the same, continue checking.
  3. Increment i and decrement j.
  4. Repeat steps 2-3 until i is greater than or equal to j.
  5. If the loop completes without finding differing characters, the string is a palindrome.

Example Code

Java

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

public class Main {
    public static void main(String[] args) {
        String str = "radar";
        boolean isPalindrome = true;
        
        for(int i = 0, j = str.length() - 1; i <= j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                isPalindrome = false;
                break;
            }
        }
        
        System.out.println("Is palindrome: " + isPalindrome);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "radar";
    bool isPalindrome = true;
    
    for(int i = 0, j = str.length() - 1; i <= j; i++, j--) {
        if (str[i] != str[j]) {
            isPalindrome = false;
            break;
        }
    }
    
    cout << "Is palindrome: " << isPalindrome << endl;
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

str_ = "radar"
is_palindrome = True

for i in range(len(str_)//2):
    j = len(str_) - 1 - i
    
    if str_[i] != str_[j]:
        is_palindrome = False
        break

print("Is palindrome:", is_palindrome)

Key Takeaways

  • The for loop efficiently checks each pair of characters from opposite ends.
  • The loop stops as soon as a non-matching pair is found, making the check fast.
  • This method only requires a single pass through the string, making it time-efficient.