{"id":"0564bddb-8e50-4ca8-a3f7-fb1829124a51","name":"Partition An Array","description":"1. You are given an array(arr) of integers and a pivot.\r\n2. You have to re-arrange the given array in such a way that all elements smaller or equal to pivot lie on the left side of pivot and all elements greater than pivot lie on its right side.\r\n3. You have to achieve this in linear time.\r\n\r\nNote -> For more information, watch question video.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers\r\nAn integer pivot","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 100000\r\n-10^9 &lt;= arr[i] &lt;= 10^9\r\n-10^9 &lt;= pivot &lt;= 10^9","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n\nvoid swap(int arr[],int i,int j){\n cout<<\"Swapping \"<<arr[i]<<\" and \"<<arr[j]<<endl;\n int temp=arr[i];\n arr[i]=arr[j];\n arr[j]=temp;\n}\n\nvoid partition(int arr[],int n,int pivot){\n // write your code\n}\n\nvoid print(int arr[],int n){\n for(int i=0;i<n;i++){\n cout<<arr[i]<<\" \";\n }\n cout<<endl;\n}\n\nint main(){\n \n int n;\n cin>>n;\n \n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n \n int pivot;\n cin>>pivot;\n \n partition(arr,n,pivot);\n print(arr,n);\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void partition(int[] arr, int pivot){\r\n //write your code here\r\n \r\n }\r\n\r\n // used for swapping ith and jth elements of array\r\n public static void swap(int[] arr, int i, int j) {\r\n System.out.println(\"Swapping \" + arr[i] + \" and \" + arr[j]);\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\r\n }\r\n\r\n public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.print(arr[i] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n int pivot = scn.nextInt();\r\n partition(arr,pivot);\r\n print(arr);\r\n }\r\n\r\n}"},"python":{"code":"def swap(arr,i,j):\n print(\"Swapping\",arr[i],\"and\",arr[j])\n temp=arr[i]\n arr[i]=arr[j]\n arr[j]=temp\n\n\ndef partition(arr,pivot):\n # write your code\n\n\n\ndef printList(arr):\n\tfor i in range(len(arr)):\n\t\tprint(arr[i], end=\" \")\n\tprint()\n\n\n\narr = []\n\nn = int(input())\n\nfor i in range(0, n):\n\tele = int(input())\n\n\tarr.append(ele) \n\n\npivot = int(input())\n\npartition(arr,pivot)\nprintList(arr)"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3\r\n3","sampleOutput":"Swapping -2 and 7\r\nSwapping 1 and 7\r\nSwapping 3 and 4\r\n-2 1 3 7 4","questionVideo":"https://www.youtube.com/embed/if40LxQ8_Xo?end=31","hints":[],"associated":[{"id":"8f0c2b28-cc45-4656-8159-0286e74e42cd","name":"can it be solved through two pointer approach?","slug":"can-it-be-solved-through-two-pointer-approach","type":4},{"id":"c94bae51-4720-44a0-a151-8da68f52e842","name":"What is the position of pivot element after partitioning an array?","slug":"what-is-the-position-of-pivot-element-after-partitioning-an-array","type":4},{"id":"dc676b8c-0860-4c04-87f7-340b39d4e1a8","name":"What is the Time Complexity for partition an array?","slug":"what-is-the-time-complexity-for-partition-an-array","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8e3abac7-a5ab-4090-abd1-b26ef8b53d70","name":"Time and Space Complexity","slug":"time-and-space-complexity","type":0},{"id":"9e7f1a28-14c1-41ff-a78f-220a3f6e8219","name":"Partition An Array","slug":"partition-an-array","type":1}],"next":{"id":"15c569d6-e2ea-49fd-8c25-0571145cacbe","name":"Partition An Array","type":3,"slug":"partition-an-array"},"prev":{"id":"dc5916ba-c7f4-41e2-84c9-3ec1bc0d4b64","name":"Merge Sort","type":3,"slug":"merge-sort"}}}

Partition An Array

1. You are given an array(arr) of integers and a pivot. 2. You have to re-arrange the given array in such a way that all elements smaller or equal to pivot lie on the left side of pivot and all elements greater than pivot lie on its right side. 3. You have to achieve this in linear time. Note -> For more information, watch question video.

{"id":"0564bddb-8e50-4ca8-a3f7-fb1829124a51","name":"Partition An Array","description":"1. You are given an array(arr) of integers and a pivot.\r\n2. You have to re-arrange the given array in such a way that all elements smaller or equal to pivot lie on the left side of pivot and all elements greater than pivot lie on its right side.\r\n3. You have to achieve this in linear time.\r\n\r\nNote -> For more information, watch question video.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers\r\nAn integer pivot","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 100000\r\n-10^9 &lt;= arr[i] &lt;= 10^9\r\n-10^9 &lt;= pivot &lt;= 10^9","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n\nvoid swap(int arr[],int i,int j){\n cout<<\"Swapping \"<<arr[i]<<\" and \"<<arr[j]<<endl;\n int temp=arr[i];\n arr[i]=arr[j];\n arr[j]=temp;\n}\n\nvoid partition(int arr[],int n,int pivot){\n // write your code\n}\n\nvoid print(int arr[],int n){\n for(int i=0;i<n;i++){\n cout<<arr[i]<<\" \";\n }\n cout<<endl;\n}\n\nint main(){\n \n int n;\n cin>>n;\n \n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n \n int pivot;\n cin>>pivot;\n \n partition(arr,n,pivot);\n print(arr,n);\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void partition(int[] arr, int pivot){\r\n //write your code here\r\n \r\n }\r\n\r\n // used for swapping ith and jth elements of array\r\n public static void swap(int[] arr, int i, int j) {\r\n System.out.println(\"Swapping \" + arr[i] + \" and \" + arr[j]);\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\r\n }\r\n\r\n public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.print(arr[i] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n int pivot = scn.nextInt();\r\n partition(arr,pivot);\r\n print(arr);\r\n }\r\n\r\n}"},"python":{"code":"def swap(arr,i,j):\n print(\"Swapping\",arr[i],\"and\",arr[j])\n temp=arr[i]\n arr[i]=arr[j]\n arr[j]=temp\n\n\ndef partition(arr,pivot):\n # write your code\n\n\n\ndef printList(arr):\n\tfor i in range(len(arr)):\n\t\tprint(arr[i], end=\" \")\n\tprint()\n\n\n\narr = []\n\nn = int(input())\n\nfor i in range(0, n):\n\tele = int(input())\n\n\tarr.append(ele) \n\n\npivot = int(input())\n\npartition(arr,pivot)\nprintList(arr)"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3\r\n3","sampleOutput":"Swapping -2 and 7\r\nSwapping 1 and 7\r\nSwapping 3 and 4\r\n-2 1 3 7 4","questionVideo":"https://www.youtube.com/embed/if40LxQ8_Xo?end=31","hints":[],"associated":[{"id":"8f0c2b28-cc45-4656-8159-0286e74e42cd","name":"can it be solved through two pointer approach?","slug":"can-it-be-solved-through-two-pointer-approach","type":4},{"id":"c94bae51-4720-44a0-a151-8da68f52e842","name":"What is the position of pivot element after partitioning an array?","slug":"what-is-the-position-of-pivot-element-after-partitioning-an-array","type":4},{"id":"dc676b8c-0860-4c04-87f7-340b39d4e1a8","name":"What is the Time Complexity for partition an array?","slug":"what-is-the-time-complexity-for-partition-an-array","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8e3abac7-a5ab-4090-abd1-b26ef8b53d70","name":"Time and Space Complexity","slug":"time-and-space-complexity","type":0},{"id":"9e7f1a28-14c1-41ff-a78f-220a3f6e8219","name":"Partition An Array","slug":"partition-an-array","type":1}],"next":{"id":"15c569d6-e2ea-49fd-8c25-0571145cacbe","name":"Partition An Array","type":3,"slug":"partition-an-array"},"prev":{"id":"dc5916ba-c7f4-41e2-84c9-3ec1bc0d4b64","name":"Merge Sort","type":3,"slug":"merge-sort"}}}
plane

Editor

Loading...

Partition An Array

easy

1. You are given an array(arr) of integers and a pivot. 2. You have to re-arrange the given array in such a way that all elements smaller or equal to pivot lie on the left side of pivot and all elements greater than pivot lie on its right side. 3. You have to achieve this in linear time. Note -> For more information, watch question video.

Constraints

1 <= N <= 100000 -10^9 <= arr[i] <= 10^9 -10^9 <= pivot <= 10^9

Format

Input

An Integer n arr1 arr2.. n integers An integer pivot

Output

Check the sample output and question video.

Example

Sample Input

5 7 -2 4 1 3 3

Sample Output

Swapping -2 and 7 Swapping 1 and 7 Swapping 3 and 4 -2 1 3 7 4

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode