Scribd
Upload
4 views1 page

Build Array from Permutation in Java

The document describes a Java solution for building a new array based on a given array using two methods: a brute force approach and a more efficient method. The brute force method involves creating a new array and iterating through the original array, while the better solution modifies the original array in place to store both old and new values. The time complexity is O(N) and the space complexity is O(N) for the brute force method, while the better solution optimizes space usage.

Uploaded by

wedok26771
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
4 views1 page

Build Array from Permutation in Java

The document describes a Java solution for building a new array based on a given array using two methods: a brute force approach and a more efficient method. The brute force method involves creating a new array and iterating through the original array, while the better solution modifies the original array in place to store both old and new values. The time complexity is O(N) and the space complexity is O(N) for the brute force method, while the better solution optimizes space usage.

Uploaded by

wedok26771
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

class Solution {

// brute force:
// step 1: take the new array of the same size of the given array
// step 2: itterate the loop on the given array
// step 3: apply the said statement and store the value of the perticular array
index
// step 4: at end of the loop return the new array
// time complexity: O(N);
// space complexity: O(N);
public int[] buildArray(int[] nums) {
// int[] ans= new int[[Link]];
// for(int i=0; i<[Link];i++){
// ans[i]=nums[nums[i]];
// }
// return ans;

// better solution:
// intuition: store the old and new number at the one place and then
extract the required value as per the convient
int n=[Link];
for(int i=0;i<n;i++){
nums[i]=nums[i]+n * (nums[nums[i]]%n);
}

for(int i=0;i<n;i++){
nums[i]/=n;
}

return nums;
}
}

You might also like