Common minimum

commonMinimum.cs

using System;
using System.Collections.Generic;
using System.Linq;

/*
Common-minimum problem:

Write a function:
         int solution(int A[], int B[]);
 
that, given a non-empty zero-indexed array A of N non-negative integers and
a non-empty zero-indexed array B of M non-negative integers, 
returns the minimal value that occurs in both arrays. 
If there is no such value, the function should return -1.

*/

namespace CommonMinimum
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // int[] A = new int[]{1, 2, 2, 4, 5};
            // int[] B = new int[]{3, 4, 1, 2, 5};
            
            int[] A = new int[]{11, 3, 5};
            int[] B = new int[]{7, 9, 6, 4};
            
            test(A, B);
        }
        
        static void test(int[] A, int[] B) {
            Console.WriteLine("Common minium using Approach 1 is {0}", solution1(A, B));
            Console.WriteLine("Common minium using Approach 2 is {0}", solution2(A, B));
        }
        
        // Time: O(nlogn)
        // Space: O(1)
        static int solution1(int[] A, int[] B) {
            Array.Sort(A);
            Array.Sort(B);
            
            int i = 0;
            int j = 0;
            
            while (i < A.Length && j < B.Length) {
                if (A[i] == B[j]) {
                    return A[i];
                } else if (A[i] < B[j]) {
                    i++;
                } else {
                    j++;
                }
            }
            
            return -1;
        }
        
        // Time: O(n)
        // Space: O(n)
        static int solution2(int[] A, int[] B) {
            HashSet<int> mapA = new HashSet<int>(A);
            
            int minimum = Int32.MaxValue;
            foreach(int val in B) {
                if (mapA.Contains(val) && val < minimum) {
                    minimum = val;
                }
            }
            
            if (minimum == Int32.MaxValue) {
                minimum = -1;
            }
            
            return minimum;
        }
    }
}