Validate array symmetric

Question

Determine if a given array satisfies the symmetric property.

Codemia · Accepted Answer

To determine if an array is symmetric, we need to check if the elements are the same when read from the front and the back. This suggests a **two-pointer** strategy, where one pointer starts from the beginning of the array and another from the end. This approach is effective here because we can simultaneously check corresponding elements from both ends of the array, making it efficient and straightforward.

Here’s a step-by-step algorithm:
1. Initialize two pointers: one (`left`) at the start of the array (index 0) and the other (`right`) at the end of the array (index n-1).
2. While `left` is less than `right`, do the following:
   - Check if the elements at these pointers are equal (`array[left] == array[right]`).
   - If they are not equal, return `False` as the array is not symmetric.
   - If they are equal, increment `left` by 1 and decrement `right` by 1.
3. If the loop completes without finding unequal elements, return `True` as the array is symmetric.

**Example:** For the array [1, 2, 3, 2, 1]:
- Start with `left = 0` (1) and `right = 4` (1) -> equal, move pointers.
- Now `left = 1` (2) and `right = 3` (2) -> equal, move pointers.
- Finally, `left = 2` (3) and `right = 2` (3) -> equal, pointers meet, return `True`.

Here's the implementation in Python:
```python
def is_symmetric(array):
    left, right = 0, len(array) - 1
    while left < right:
        if array[left] != array[right]:
            return False
        left += 1
        right -= 1
    return True
```
This code checks the symmetry of the array in O(n) time, where n is the length of the array.

The time complexity of this solution is O(n) because we potentially check each element once. The space complexity is O(1) since we are using only a fixed amount of extra space for the pointers, regardless of the input size. This is optimal for this problem since we need to inspect each element in the worst case.

Consider the following edge cases specific to this problem:
1. An empty array `[]` should return `True` as it is symmetric by definition.
2. An array with one element `[1]` should also return `True`.
3. An array with two different elements `[1, 2]` should return `False`.
4. An array with two identical elements `[1, 1]` should return `True`.
5. Arrays with odd lengths, such as `[1, 2, 3, 2, 1]`, should be checked for symmetry correctly, returning `True`.

Validate array symmetric

Citadel

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Citadel Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string