FilesExpand file tree

 master

/

RearrangeArrayPerIndex.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (44 loc) · 1.26 KB

 master

/

RearrangeArrayPerIndex.java

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (44 loc) · 1.26 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

package com.interview.array;

import java.util.Arrays;

/**

* Date 12/30/2015

*

* Given an array of size n where elements are in range 0 to n-1. Rearrange elements of array

* such that if arr[i] = j then arr[j] becomes i.

*

* Time complexity O(n)

* Space complexity O(1)

*

* http://www.geeksforgeeks.org/rearrange-array-arrj-becomes-arri-j/

*/

public class RearrangeArrayPerIndex {

public void rearrange(int input[]) {

for (int i = 0; i < input.length; i++) {

input[i]++;

}

for (int i = 0; i < input.length; i++) {

if (input[i] > 0) {

rearrangeUtil(input, i);

}

}

for (int i = 0; i < input.length; i++) {

input[i] = -input[i] - 1;

}

}

private void rearrangeUtil(int input[], int start) {

int i = start + 1;

int v = input[start];

while (v > 0) {

int t = input[v - 1];

input[v - 1] = -i;

i = v;

v = t;

}

}

public static void main(String args[]) {

RearrangeArrayPerIndex rai = new RearrangeArrayPerIndex();

int input[] = {1, 2, 0, 5, 3, 4};

rai.rearrange(input);

Arrays.stream(input).forEach(i -> System.out.print(i + " "));

}

}