Minimum Size Subarray containing Subsequence


  • 0

    Given an array nums and a subsequence sub, find the shortest subarray of nums that contains sub.

    Example: nums = [1,2,3,5,8,7,6,9,5,7,3,0,5,2,3,4,4,7], sub = [5,7]
    Answer: start = 8, size = 2

    If such subarray does not exist, return -1, -1.
    Note that the subarray must contain the elements of sub in the correct order..


  • 0
    R

    @agave The order of sub that needs to be present in the nums should be in the same sequence?


  • 0
    public static string FindShortestSubArray(int[] nums, int[] sub)
    		{
    			int j = 0;
    			int Index = -1; int minIndex = -1;
    			int size = 0; int minSize = -1;
    			 
    			bool countSize = false;
    
    
    			for (int i = 0; i < nums.Length; i++)
    			{
    				if (sub[j] == nums[i])
    				{
    					if (j == 0) { Index = i; }
    
    					j++; countSize = true;
    				}
    				else
    				{
    					if (nums[i] == sub[0] && j == 1) { Index = i; j = 0; size = 0; j++; countSize = true; }
    				}
    
    
    				if (countSize == true)
    				{
    					size++;
    				}
    
    				if (j == sub.Length)
    				{
    					if ((minSize > size) || (minSize == -1 && minIndex == -1))
    					{
    						minIndex = Index;
    						minSize = size;
    					}
    
    					j = 0; size = 0; countSize = false;
    				}
    			}
    
    
    			return minIndex.ToString() + ' ' + minSize.ToString();
    		}
    

  • 0
    A
    public static void findSubArray(int[] in, int[] sub) {
    		int i = 0, j = 0;
    		int lastMinSubSize = Integer.MAX_VALUE;
    		int startpos = -1;
    		while (i < in.length) {
    			int cnt = 0;
    			while (j < sub.length && i < in.length) {
    				if (sub[j] == in[i]) {
    					break;
    				}
    				i++;
    			}
    			if(i >= in.length) {
    				break;
    			}
    			int start = i;
    			cnt = 1;
    			while (j < sub.length && i < in.length) {
    				if (sub[j] != in[i]) {
    					i++;
    					cnt++;
    				} else {
    					j++;
    				}
    			}
    			
    			if(j == sub.length) {
    				if(lastMinSubSize > cnt) {
    					lastMinSubSize = cnt;
    					startpos = start;
    				}
    			}
    			
    			j = 0;
    			i = start+1;
    		}
    
    		if(startpos == -1) {
    			lastMinSubSize = -1;
    		}
    		
    		System.out.println(startpos + " " +lastMinSubSize);
    	}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.