[Leetcode] 1920. Build Array from Permutation

https://leetcode.com/problems/build-array-from-permutation/?envType=daily-question&envId=2025-05-06

initial

so there is a very obious brute force approach but lets think about this

sol

but to do in o(1) memory we have to modify the given list. How? while retaining the original number?

a=bq+r

So the way to "encode" the original number is to kinda use it as a remainder where qb+r where q=quotient=len(nums), b=new number, r=old number

no matter if we r%q, we still get r if q is bigger than r. So q has to be the len(nums) cuz r is guaranteed to be less than q.

As we update the new number with iteration we have to modulo by q cuz the numbers that we get with index might have been already updated with this formula.

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        q=len(nums)
        # qb+r where q=quotient=len(nums), b=new number, r=old number
        for i in range(len(nums)):
            r=nums[i]
            b=nums[nums[i]]%q
            nums[i]=b*q+r
        for i in range(len(nums)):
            nums[i]= nums[i]//q
        return nums

complexity

n time
1 space