educative.io

First Non-Repeating Integer in an Array - Is this O(n^2) ? Any better soln?

Courses
,
#1

Hello - is there any better solution for this problem? It seem like O(n^2).

for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
…
}
}

#2

package xyz;

import java.util.ArrayList;

import java.util.List;

import java.util.ListIterator;

public class Solution {

public static void main(String[] args) {

int [] arr = {9, 2, 3, 2, 6, 6};

System. out .println( findFirstUnique (arr));

}

public static int findFirstUnique( int [] arr)

{ int len = arr.length - 1;

List<Integer> distinct = new ArrayList<Integer>(len);

// write your code here

for ( int i = 0; i < len; i++){

if (distinct.contains(arr[i])){

distinct.remove(arr[i]);

}

else

{

distinct.add(arr[i]);

}

}

ListIterator<Integer> iterator = distinct.listIterator();

int result = 0;

while (iterator.hasNext()){

result = iterator.next();

break ;

}

return result;

}

}

#3

Hello,
Please try this logic it solves in one pass i.e, O(n)

public static int findFirstUnique(int[] arr)
{
int result = arr[0];
// write your code here
for(int i=1;i<arr.length;i++)
{
result=result^arr[i];
}
return result;
}

#4

@Achyuth_Balanthrapu I don’t understand your code. It doesn’t appear to find the first non-repeating integer. Could you please explain this?

#5

In your findFirstUnique( int [] arr) method, you have not initialized you list with the passed array. What will your iterator object use to check for the next element when calling .next()

Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers