Blogs Hub

Element Appearing More Than 25% In Sorted Array - Easy - LeetCode - MiniTV

Element Appearing More Than 25% In Sorted Array - Easy - LeetCode - मिनी टीवी

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

 

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]

Output: 6

 

Constraints:

1 <= arr.length <= 10^4

0 <= arr[i] <= 10^5

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
    public class FindSpecialIntegerSoln
    {
        public int FindSpecialInteger(int[] arr)
        {
            var map = new Dictionary<int, int>();
            
            for (int i = 0; i < arr.Length; i++)
            {
                if (map.ContainsKey(arr[i]))
                {
                    map[arr[i]]++;
                }
                else
                {
                    map.Add(arr[i], 1);
                }
            }

            // As it is mentioned that there will be at least one number
            // that will be having more than 25% frequency count.
            int max = 0;
            int value = 0;
            foreach (var item in map)
            {
                if (max < item.Value)
                {
                    max = item.Value;
                    value = item.Key;
                }
            }

            return value;
        }
    }
}

 

Time Complexity: O(n)

Space Complexity: O(n)

 

Unit Tests:

using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
    [TestClass]
    public class FindSpecialIntegerSolnTests
    {
        [TestMethod]
        public void FindSpecialIntegerSoln_First()
        {
            var arr = new int[] { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
            var output = 6;
            var res = new FindSpecialIntegerSoln().FindSpecialInteger(arr);

            Assert.AreEqual(res, output);
        }
    }
}