Non-decreasing array after 1 or less swap


  • 1
    N

    A non-empty zero-indexed array A consisting of N integers is given. You can performance 1 or less swap operation in array A. The goal is to check whether array A can be non-decreasing order after 1 or less swap.

    Example: [1,5,8,3] => false
    [3,2,1] => true
    It was from Samsung OA.


  • 0
    This post is deleted!

  • 0

    @nullpointerP can you exmplin please, why example [1,5,8,3] is true. How does it becomes [1,3,5,8] with one swap?
    Actually the same problem is with [3,2,1] . Here the answer should be true, because [3,2,1] becomes [1,2,3] with 1 swap


  • 0

    An implementation. Search for maximum two inversions. Keep the positions at which inversions happens and swap. Then check if array is in ascendng way O(n)

                   boolean isNonDecreasing(int[] nums) {			
    			if (nums.length <= 1)
    				return true;
    			int s =  0;			
    			int cnt = 0;
    			int[] swaps = new int[2];			
    			while (s < nums.length - 1) {
    				if (nums[s] > nums[s + 1]) {				
    					if (cnt == 2)
    						return false;
    					else {						
    						swaps[cnt] = s;
    						cnt++;
    					}
    				}
    				s++;
    			}
    			if (cnt == 0)
    				return true;
    			if (cnt <= 2) {				
    				if (cnt == 1) {
    	 				int res = Arrays.binarySearch(nums, nums[swaps[0] + 1]);
    					if (res < 0) {
    						res = -res;	
    						res -= 1;
    					} else  
    						res += 1;
    					swap(res, swaps[0] + 1, nums);
    							
    				}			
    				else if (cnt == 2) 				
    					swap(swaps[0], swaps[1] + 1, nums);			
    				s = 0;
    				while (s < nums.length - 1) {
    					if (nums[s] > nums[s + 1]) 
    						return false;
    					s++;
    				}
    				return true;
    			}
    			else
    				return false;	
    
    		}
    

  • 0
    N

    @elmirap I am sorry I entered the wrong result. I have already modified it. Thanks!


  • 0

    @nullpointerP welcome


  • 0
    L
    def check_one_swap(s):
    	n = len(s)
    	first = second = -1
    	if n == 1:
    		return true
    	for i in range(n-1):
    		if s[i+1] >= s[i]:
    			continue
    		else:
    			if first == -1:
    				first = i
    				second = i + 1
    			elif second == first + 1:
    				second = i + 1
    			else:
    				return false
    	return s[first] >= s[second - 1] and s[second] <= s[first + 1] and (True if first == 0 else s[second] >= s[first - 1]) and (True if second == n -1 else s[first] <= s[second + 1])
    

Log in to reply
 

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