# Re: Finding a constant-space algorithm

*From*: Lie Ryan <lie.1296@xxxxxxxxx>*Date*: Fri, 25 Dec 2009 09:34:29 +1100

On 12/25/2009 7:31 AM, Richard Harter wrote:

On Fri, 25 Dec 2009 07:02:39 +1100, Lie Ryan<lie.1296@xxxxxxxxx>

wrote:

The problem description:

"""

Return an array that contains exactly the same numbers as the given

array, but rearranged so that every 4 is immediately followed by a 5. Do

not move the 4's, but every other number may move. The array contains

the same number of 4's and 5's, and every 4 has a number after it that

is not a 4. In this version, 5's may appear anywhere in the original array.

http://www.javabat.com/prob/p125819

"""

Big Juicy Hint: Use two pointers, one for 4's and one for 5's.

Try to work it out for yourself.

Solution: (rot 13)

Fgneg ol svaqvat gur svefg 4 naq gura svaq gur svefg 5. Fjnc gur

svefg 5. Gurernsgre frnepu sbe gur arkg 4 nsgre fjnccvat n 5.

Jura lbh svaq n 4, frnepu sbe gur arkg 5 naq fjnc vg. Jura lbh

eha bhg bs 4'f lbh ner qbar.

It's a cute puzzle. There is a general programming trick of the

trade here. When scanning data it can pay to use multiple

pointers.

Sorry mate, it's not that easy (you didn't think I haven't tried that approach before, did you?). That only solves the slightly easier version fix34 but not this fix45:

public int[] fix45(int[] nums) {

int five = 0;

int four = 0;

for (; four < nums.length; four++) {

if (nums[four] == 4) {

for (; five < nums.length && nums[five] != 5; five++);

swap(nums, four + 1, five);

}

}

return nums;

}

public void swap(int[] nums, int a, int b) {

int tmp = nums[a];

nums[a] = nums[b];

nums[b] = tmp;

}

specifically the naive attempt doesn't pass these:

* unittest * * result *

fix45({5, 4, 9, 4, 9, 5}) → {9, 4, 5, 4, 5, 9} {9, 4, 9, 4, 5, 5}

fix45({4, 5, 4, 1, 5}) → {4, 5, 4, 5, 1} {4, 1, 4, 5, 5}

Adding the "in-place restriction" is what makes it extremely difficult; in the website I mentioned the online unittest uncovers many subtleties that you won't think of until you tried it yourself. I already have quite a few versions that either doesn't pass all the tests or "cheats"[1] or doesn't work in-place.

[1] by making assumptions that aren't specified in the problem description

.

**Follow-Ups**:**Re: Finding a constant-space algorithm***From:*Patricia Shanahan

**References**:**Finding a constant-space algorithm***From:*Lie Ryan

**Re: Finding a constant-space algorithm***From:*Richard Harter

- Prev by Date:
**Re: Finding a constant-space algorithm** - Next by Date:
**Re: Finding a constant-space algorithm** - Previous by thread:
**Re: Finding a constant-space algorithm** - Next by thread:
**Re: Finding a constant-space algorithm** - Index(es):