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])
    

  • 0
    L

    @elmirap
    int res = Arrays.binarySearch(nums, nums[swaps[0] + 1]);
    if (res < 0) {
    res = -res;
    res -= 1;
    } else
    res += 1;
    In this code block, how can res be negative? since you are searching for an element in the array.


Log in to reply
 

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