702722. Left or Right Positioned Array
Left or Right Positioned Array
Slug: left-or-right-positioned-array5757
Difficulty: Easy
Id: 702722
Topic Tags: Arrays, Data Structures
Company Tags: None
Summary
The problem involves an array of integers where each element is either positioned to the left or right of its corresponding index. The goal is to determine whether all elements in the array are correctly positioned or not.
Detailed Explanation
Given an integer array arr[], we need to check if all elements are either left or right positioned. An element is considered left-positioned if it's at an even index and greater than or equal to its corresponding value, whereas an element is considered right-positioned if it's at an odd index and less than or equal to its corresponding value.
Here's a step-by-step breakdown of the solution:
- Iterate through the array from the first element to the second last element (inclusive).
- For each element, check if it's left-positioned or right-positioned using the above conditions.
- If an element is not positioned correctly, immediately return
falseas all elements must be either left or right positioned. - After iterating through the entire array, if no incorrect positions were found, return
true.
Time complexity: O(n), where n is the size of the input array.
Space complexity: O(1), as we only use a constant amount of space to store variables.
Optimized Solutions
Java
public boolean checkPosition(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if ((i % 2 == 0 && arr[i] >= arr[i + 1]) || (i % 2 != 0 && arr[i] <= arr[i + 1])) {
continue;
}
return false;
}
return true;
}