PermMissingElem – Codility – Solution

Java solution to Codility PermMissingElem (Permutation Missing Element) problem (Lesson 3 – Time Complexity) which scored 100%. The problem is to find the missing element in a given permutation. The main strategy is use a HashSet to store elements which will also order them. Then check all values from 1 to max to see if it’s missing from HashSet.

[cc lang="java" escaped="true"]
package com.codility.lesson03.timecomplexity;

import java.util.HashSet;
import java.util.Set;

public class PermutationMissingElement {
	public int solution(int[] A) {
		int max = A.length + 1;
		
		//load array elements into array so would be quick to check if elements exist
		Set incompleteSet = new HashSet();
		for(int i=0; i<A.length; i++) {
			incompleteSet.add(A[i]);
		}

		for(int i=1; i<max+1; i++) {
			if(!incompleteSet.contains(i)) {
				return (i);
			}
		}
		throw new RuntimeException("shouldn't reach here");
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson03.timecomplexity;

import org.testng.Assert;
import org.testng.annotations.*;

import com.codility.lesson03.timecomplexity.PermutationMissingElement;

public class PermutationMissingElementTests {
	private PermutationMissingElement solution;
	
	@BeforeTest
	public void setUp() {
		solution = new PermutationMissingElement();
	}
	
	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] { new int [] {                        }, 1 },
			new Object [] { new int [] {                      1 }, 2 },
			new Object [] { new int [] {                      2 }, 1 },
			new Object [] { new int [] {                   1, 3 }, 2 },
			new Object [] { new int [] {                   2, 3 }, 1 },
			new Object [] { new int [] {                1, 2    }, 3 },
			new Object [] { new int [] {                1, 3, 4 }, 2 },
			new Object [] { new int [] {                2, 4, 3 }, 1 },
			new Object [] { new int [] {             2, 3, 1, 5 }, 4 },
			new Object [] { new int [] { 4, 2, 3, 1, 5, 6, 8, 9 }, 7 },
			new Object [] { new int [] { 4, 2, 3, 1, 5, 6, 8, 7 }, 9 },
		};
	}

	@Test(dataProvider = "test1")
	public void verifySolution(int [] pA, int pExpectedMissingValue) {
		Assert.assertEquals(solution.solution(pA), pExpectedMissingValue);
	}
}
[/cc]