DEV Community: Vishnu S Reddy

Build Array from Permutation – Solution to LeetCode Problem

Vishnu S Reddy — Wed, 07 Jul 2021 08:59:22 +0000

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).

Examples

Example 1

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows: 
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

Example 2

Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

Constraints

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
The elements in nums are distinct.

Follow Up

Can you solve it without using an extra space (i.e., O(1) memory)?

I highly recommend you to try solving this problem on LeetCode.

Approach 1

One very simple idea is to create a new list. Create a loop with loop control variable i from 0 to len(nums). For each i, append nums[nums[i]] to the new list.

Solution in Python

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(0, len(nums)):
            res.append(nums[nums[i]])
        return res

While this has a time complexity of O(n), it has a space complexity of O(n) because it needs additional space to store the new list.

Approach 2

This solution makes use of the modulo operator. Using the properties of Modulo, we can store two numbers in one element and extract them at our will. We are given that the range of nums[i] is between 0 to 1000. So we take modulo to be 1001.

As the values in the input array are ranging from 0 to n-1 where n is the length of the array, we can simply store the input array value in modulo by n and modified value in divide by n. This solves the problem of adding extra space to our solution.

We make use of the equation nums[i] = nums[i] + (n*(nums[nums[i]]%n)) to store the new values in the nums array. We then divide by n to get the required value to return.

To understand this better, let’s assume an element is a and another element is b, both the elements are less than n. So if an element a is incremented by b*n, the element becomes a + b*n. So, when a + b*n is divided by n, the value is b and a + b*n % n is a.

Example

Consider the input array as [1, 0]. Now in each iteration (0 to len(nums)-1), we use the equation shown above to make the array as shown below.

nums[i] = nums[i] + (n*(nums[nums[i]]%n))
After running the loop, the array becomes [1, 2].

After dividing by 2 it results in [0, 1] which is the correct answer.

Solution in Python

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(0, len(nums)):
            nums[i]=nums[i]+(n*(nums[nums[i]]%n))

        for i in range(0, len(nums)):
            nums[i] = int(nums[i]/n)

        return nums

Solution in C++

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n=nums.size();
        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;
    }
};

The space complexity of this approach is O(1) and the time complexity is O(n). The basic idea to remember here is that we have to make use of the modulo operator to store two values in the same element.

I hope you understood the concepts involved, if not, please do comment below. If you liked my work, you can buy me a pizza here.

This post was originally published on hello ML.

How to create your first Django app on Windows?

Vishnu S Reddy — Sun, 24 May 2020 19:36:38 +0000

Hey, this is just a small article to help you create your first Django app. Django is a high-level Python Web framework that encourages rapid development and clean, pragmatic design. Built by experienced developers, it takes care of much of the hassle of Web development, so you can focus on writing your app without needing to reinvent the wheel. It’s free and open source.

Let's get started.

Download and install Python if you don't already have it by clicking here and verify by going to command prompt and type

python --version

Then make sure that pip is installed by typing pip --verison in the terminal.

pip --version

Now install the virtual environment.

pip install virtualenvwrapper-win
mkvirtualenv <name>

Now we install Django

pip install django
django-admin --verison

Now we create a project called prj in a folder called projects

mkdir projects
cd projects

django-admin startproject prj
cd prj

To check the installation type

python manage.py runserver

If everything works fine, you should see this

Watching for file changes with StatReloader
Performing system checks...

System check identified no issues (0 silenced).

You have 17 unapplied migration(s). Your project may not work properly until you apply the migrations for app(s): admin, auth, contenttypes, sessions.
Run 'python manage.py migrate' to apply them.
May 25, 2020 - 00:51:11
Django version 3.0.6, using settings 'prj.settings'
Starting development server at http://127.0.0.1:8000/
Quit the server with CTRL-BREAK.

Now when you go the link i.e HTTP://127.0.0.1:8000/ on your browser you should see this

Now let's create your app
Go to the terminal and type

python manage.py startapp appname

So now we have created an app called appname.
Let us make this app to print some text like Hello world.
Open your code editor and create a file called urls.py inside appname folder and put int the following code

from django.contrib import admin
from django.urls import path
from . import views
urlpatterns = [
path('',views.home, name="home"),
path('admin/', admin.site.urls),
]

Now go the views.py file and put in the following code:

from django.shortcuts import render
from django.http import HttpResponse

def home(request):
    return HttpResponse("Hello World")

Now in the urls.py file in the project ( Not in the app that we created)

from django.contrib import admin
from django.urls import path, include

urlpatterns = [
path('', include('appname.urls')),
]

Now go to the terminal and run the server by typing

python manage.py runserver

Now go to HTTP://127.0.0.1:8000/ and you should be able to see Hello World.
Congratulations, you have just created your first Django app.
In my next article I will explain about DTL i.e Django Template Language.