Category Archives: Java

Majority Element II | N/3 Repeated Number

By | | , ,
Leave a comment

In this tutorial, I am going to discuss a very interesting problem find N/3 repeated number in an array.

Given an array of size n, Write a code to find all the elements that appear more than n/3 times.

NOTE: We have to solve this problem in linear time and in O(1) space.

Example 1:

Input : [3, 2, 3]

Output: 3

In this example, The size of this array is 3. We have to find all the numbers which occurred more than n/3 where n is the size of the array. The number 3 appears more than 1 times.

Example 2:

Input: [1, 1, 1, 3, 3, 2, 2, 2]

Output:[1, 2]

→

Recover Binary Search Tree

By | | , , ,
Leave a comment

In this problem, we have given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Write a code to recover binary search tree without changing its structure.

The solution using O(n) space is pretty straight forward. Can you solve this problem using constant space?

→

Find Majority Element in an Array

By | | , ,
Leave a comment

Given an array of size n, Write a code to find majority element in an array.

What is Majority Element?

The majority element is the element that appears more than n/2 times where n is the size of an array.

NOTE: For this problem you can assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input : [3, 2, 3]

Output: 3

The size of the array is 3 and the element which occurs more than 1 is the majority element. So three is the output.

Example 2:

Input: [2, 2, 1, 1, 1, 2, 2]

Output: 2

The element 2 occurs more than 3 times. So, It is the majority element.

→