702673. Taking 1 out of 3 consecutives
Medium
Taking 1 out of 3 Consecutives
Summary
Given an array of integers, take one out of every three consecutive elements and store them in a new array. This problem involves arrays and dynamic programming.
Detailed Explanation
The key to this problem is to iterate through the input array in steps of three. For each set of three consecutive elements, choose one element to add to the result array. This can be done by iterating through the input array with a for loop and adding every third element to the result array.
Here's a step-by-step breakdown of the solution:
- Initialize an empty array
resultto store the output. - Iterate through the input array
arrin steps of three using a for loop:- For each set of three consecutive elements, choose one element (e.g., the middle one) and add it to the result array.
- Return the result array.
Time Complexity: O(n), where n is the length of the input array. Space Complexity: O(n/3), since we're storing approximately one-third of the elements in the result array.
Optimized Solutions
Java
public int[] takeOneOutOfThree(int[] arr) {
int[] result = new int[(arr.length + 2) / 3];
for (int i = 0; i < arr.length; i += 3) {
if (i + 2 < arr.length) {
result[i / 3] = arr[i + 1];
}
}
return result;
}