I tackled two data structures and algorithms (DSA) problems related to arrays today. I worked on these questions directly within my LeetCode profile.
1. Build Array from Permutation
Problem Statement: Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.
A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).
The approach I used to solve it:
Runtime: 1ms
Time complexity: O(n), where n is length of the input array.
Space Complexity: O(n), where n is the length of ans which is occupying the additional space.
class Solution {
public int[] buildArray(int[] nums) {
int[] ans = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
ans[i] = nums[nums[i]];
}
return ans;
}
}
Explanation of the above program:
The straightforward approach to solving this problem involves creating a new array, ans[], with the same size as the input array nums[]. Each element in ans[] is determined by placing the element at nums[nums[i]] into its respective position in the ans[] array.
For instance, considering the array nums[] = {5, 0, 1, 2, 3, 4} with a size of 5, the process unfolds as follows:
At index 0,
ans[0]is set tonums[nums[0]], resulting inans[0] = nums[5] = 4.Moving to index 1,
ans[1]is determined asnums[nums[1]], yieldingans[1] = nums[0] = 5.Similarly, at index 2,
ans[2]is computed asnums[nums[2]], leading toans[2] = nums[1] = 0.This process continues until the final answer is obtained:
ans[] = {4, 5, 0, 1, 2, 3}.
This approach efficiently rearranges the elements of the array based on their corresponding values, ultimately achieving the desired outcome.
Optimized approach:
Runtime: 0ms
class Solution {
public int[] buildArray(int[] nums) {
// Using O(1) space complexity
func(nums, 0);
return nums;
}
public void func(int[] nums, int i) {
if(i < nums.length) {
int key = nums[i];
int res = nums[key];
func(nums, i + 1);
nums[i] = res;
}
}
}
The presented approach employs recursion to iteratively identify a key and a result (res) during each iteration. The key represents the element at the ith index, while the result (res) stores the final value, which corresponds to the element at nums[key].
The subsequent step involves invoking a recursive function, func(), which takes the nums array. With each function call, the index (i) is incremented to refer to the next element in the nums array. As long as the condition (i < nums.length) holds true, the control returns to the previous function call, eventually updating the nums array with each result.
Illustrating this with the example nums[] = {5, 0, 1, 2, 3, 4}:
At i = 0, key = nums[0] = 5, res = nums[5] = 4 -> func(nums, i+1)
At i = 1, key = nums[1] = 0, res = nums[0] = 5 -> func(nums, i + 1)
At i = 2, key = nums[2] = 1, res = nums[1] = 0 -> func(nums, i+1)
At i = 3, key = nums[3] = 2, res = nums[2] = 1 -> func(nums, i + 1)
At i = 4, key = nums[4] = 3, res = nums[3] = 2 -> func(nums, i+1)
At i = 5, key = nums[5] = 4, res = nums[4] = 3 -> func(nums, i + 1)
Once i = 6, violating the condition, control returns to i = 5, and the value of nums at that ith index is updated with res. This process continues until it reaches the main function where it was initially called.
Time complexity: O(n), since func() is a recursive function that processes each element of the nums array at least one.
Space complexity: O(n), the space complexity of the code is determined by the maximum depth of the recursive call stack. In this case, the maximum depth corresponds to the length of the nums array which is n.
Concatenation of Array
Problem statement: Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).
Specifically, ans is the concatenation of two nums arrays.
Return the array ans.
The approach I used:
Runtime: 1 ms
Time complexity: O(n), as the for loop iterates through each element in the nums array once, n is the size of nums array.
Space complexity: O(n), its determined by the additional space required by ans array, hence the complexity O(n).
class Solution {
public int[] getConcatenation(int[] nums) {
// new array
int ans[] = new int[nums.length * 2];
for(int i = 0; i < nums.length; i++) {
ans[i] = ans[i + nums.length] = nums[i];
}
return ans;
}
}
Explanation:
In this approach, a new array ans[] is initialized with a size double that of the nums[] array. For each element at index i in the nums[] array, its value is added at two distinct positions in the ans[] array: at ans[i] and at ans[i + nums.length].
Expressed as ans[i] = ans[i + nums.length] = nums[i], this operation effectively duplicates the value of nums[i] at two different locations in the array. After this process is completed for each element, the resulting ans[] array is returned.
This strategy ensures that the final array contains the elements of the original nums[] array followed by the same elements again in the same order.
Another approach that I found worth mentioning:
class Solution {
public int[] getConcatenation(int[] nums) {
int len = nums.length;
int ans[] = new int[2 * len];
System.arraycopy(nums, 0, ans, 0, len);
System.arraycopy(nums, 0, ans, len, len);
return ans;
}
}
Here a built-in method called System.arraycopy() is used.
The System.arraycopy() method in Java is used to copy data from one array to another. It provides a fast and efficient way to copy elements from the source array to the destination array.
Syntax of System.arraycopy() :
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
// src: source array from which elements will be copied
// srcPos: starting position in the source array (src) from where elements will be copied.
// dest: destination array where elements will be copied
// destPos: This is the starting position in the destination array where elements will be copied.
// length: number of elements to be copied
In the described method, the source array is nums[], and initially, we copy a segment of nums[] starting from the 0th position. The number of elements copied equals nums.length, forming the ans[] array. Subsequently, the entire nums[] array is copied into the ans[] array again, but this time, the copying process initiates from the len position.
Time complexity: The time complexity is primarily determined by the two System.arraycopy operations, each of which takes O(len) time to copy the elements.
Space complexity: The space complexity is determined by the additional array ans of size 2 * len. Therefore, the space complexity is O(len).
Until the next update in the journey... #bytebybyte
~ Future Forward :)