CareerCup

The question is a DP problem. Take a 2D array of size row X column. For any row r, column c, the value is the maximum possible points starting from that point.
So,
For all points with x >= c or y >= r
DP[r][c] = Math.max(DP[x][y])+1

The solution is DP[0][0].

Two efficient methods:

a. Using radix sort (From front to back) : Time complexity is O(l) where l is sum of length of all strings.

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		int n = Integer.parseInt(br.readLine());
		ArrayList<String> words = new ArrayList<String>();
		for (int i = 0; i < n; ++i) {
			words.add(br.readLine());
		}
		
		ArrayList<String> result = new ArrayList<String>();
		dfs(words, result, 0);
		
		for (int i = 0; i < result.size(); ++i) {
			out.println(result.get(i));
		}
		
		out.flush();
		out.close();
		
		System.exit(0);
	}
	
	private static void dfs(ArrayList<String> words, ArrayList<String> result, int index) {
		if (words == null || words.size() == 0)
			return;
		else if (words.size() == 1) {
			result.add(words.get(0).substring(0, index));
			return;
		}
		else {
			HashMap<Character, ArrayList<String>> buckets = new HashMap<Character, ArrayList<String>>();
			for (int i = 0; i < words.size(); ++i) {
				String word = words.get(i);
				if (word.length() == index)
					throw new RuntimeException("No unique prefixes");
				char ch = word.charAt(index);
				ArrayList<String> list = null;
				if (!buckets.containsKey(ch)) {
					list = new ArrayList<String>();
					buckets.put(ch, list);
				}
				else {
					list = buckets.get(ch);
				}
				list.add(word);
			}
			Set<Character> keys = buckets.keySet();
			for (Character key:keys) {
				dfs(buckets.get(key), result, index+1);
			}
		}
	}
}

b. Using Trie : Maximum time complexity O(l) where l is sum of length of all strings.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);

		int n = Integer.parseInt(br.readLine());
		ArrayList<String> words = new ArrayList<String>();
		for (int i = 0; i < n; ++i) {
			words.add(br.readLine());
		}

		ArrayList<String> result = uniquePrefixes(words);
		if (result != null) {
			for (int i = 0; i < n; ++i) {
				out.println(result.get(i));
			}
		}

		out.flush();
		out.close();

		System.exit(0);
	}
	
	private static ArrayList<String> uniquePrefixes(ArrayList<String> words) {
		int n = words.size();
		TrieNode root = new TrieNode();
		insert(root, words);
		ArrayList<String> result = populateUniquePrefixes(root, words);
		return result;
	}

	private static void insert(TrieNode root, ArrayList<String> words) {
		if (root == null) {
			return;
		}
		else {
			for (int i = 0; i < words.size(); ++i) {
				TrieNode current = root;
				String word = words.get(i);
				for (int j = 0; j < word.length(); ++j) {
					char ch = word.charAt(j);
					if (current.children.containsKey(ch)) {
						TrieNode next = current.children.get(ch);
						next.count = next.count+1;
						current = next;
					}
					else {
						TrieNode newNode = new TrieNode(ch, 1);
						current.children.put(ch, newNode);
						current = newNode;
					}
				}
			}
		}
	}

	private static ArrayList<String> populateUniquePrefixes(TrieNode root, ArrayList<String> words) {
		ArrayList<String> result = new ArrayList<String>();
		int n = words.size();
		for (int i = 0; i < n; ++i) {
			String word = words.get(i);
			TrieNode current = root;
			StringBuffer sb = new StringBuffer();
			int j = 0;
			for (; j < word.length(); ++j) {
				char ch = word.charAt(j);
				int count = current.children.get(ch).count;
				if (count == 1) {
					sb.append(ch);
					result.add(sb.toString());
					break;
				}
				else {
					sb.append(ch);
					current = current.children.get(ch);
				}
			}
			if (j == word.length()) {
				throw new RuntimeException("No unique prefixes");
			}
		}
		
		return result;
	}
	
	private static class TrieNode {
		public char val;
		public int count = 0;
		public HashMap<Character, TrieNode> children = null;

		public TrieNode() {
			children = new HashMap<Character, TrieNode>();
		}

		public TrieNode(char val, int count) {
			children = new HashMap<Character, TrieNode>();
			this.val = val;
			this.count = count;
		}
	}
}

On solution

import java.io.*;
import java.util.*;

public class Qs5653018213089280 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; ++i)
            A[i] = Integer.parseInt(st.nextToken());

        int S = Integer.parseInt(br.readLine());

        int i = 0;
        int j = 0;
        int temp = 0;
        int count = 0;
        int minCount = N+1;
        int startIndex = -1;

        while(j < N) {
            temp += A[j];
            j++;
            
            while (temp > S && i <= j) {
                if (minCount > j-i) {
                    minCount = j-i;
                    startIndex = i;
                }
                temp -= A[i];
                i++;
            }
        }

        if (minCount == N+1)
            out.println(-1);
        else
            out.println(minCount);

        out.flush();
        out.close();

        System.exit(0);
    }
}

public int getMaxRectArea(int[] h) {
	int length = h.length;
	int[] l = new int[length];
	int[] r = new int[length];
	Stack<Element> stack = new Stack<Element>();
	for (int i = 0; i < length; ++i) {
		int curHeight = h[i];
		int count = 1;
		while(!stack.isEmpty() && stack.peek().height >= curHeight) {
			count += stack.pop().count;
		}
		stack.push(new Element(curHeight, count));
		l[i] = count-1;
	}
	stack = new Stack<Element>();
	for (int i = length-1; i >= 0; --i) {
		int curHeight = h[i];
		int count = 1;
		while(!stack.isEmpty() && stack.peek().height >= curHeight) {
			count += stack.pop().count;
		}
		stack.push(curHeight, count);
		r[i] = count-1;
	}
	int maxArea = 0;
	for (int i = 0; i < length; ++i) {
		int temp = (r[i]+l[i]+1)*h[i];
		if (maxArea < temp)
			maxArea = temp;
	}

	return maxArea;
}

public void printIndex(int[] A, int[] B){
	int a = 0;
	int b = 0;
	int lengthA = A.length;
	int lengthB = b.length;
	while(a < lengthA && b <lengthB) {
		if (A[a] == B[b]) {
			System.out.println(A[a]);
			a++;
			b++;
		}
		else if (A[a] < B[b]) {
			a++;
		}
		else {
			b++;
		}
	}
}

import java.io.*;

public class Qs4869907900530688 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String number = br.readLine();

        int length = number.length();
        if (length > 0) {
            char ch = number.charAt(length-1);
            int exchangePosition = -1;
            for (int i = length-2; i >= 0; --i) {
                if (ch > number.charAt(i)) {
                    exchangePosition = i;
                    break;
                }
            }
            if (exchangePosition == -1)
                out.println(number);
            else {
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < exchangePosition; ++i)
                    sb.append(number.charAt(i));
                sb.append(ch);
                sb.append(number.charAt(exchangePosition));
                for (int i = length-2; i > exchangePosition; --i)
                    sb.append(number.charAt(i));
                out.println(sb.toString());
            }
        }

        out.flush();
        out.close();

        System.exit(0);
    }
}

Assuming the graph is a binary tree :

boolean populateList(Node root, LinkedList<Node> list, Node start, Node end) {
		if (root != null) {
			if (root.left == null && root.right == null)
			{
				if (root == start) 
					list = new LinkedList<Node>();
				if (list != null)
					list.add(root);
				if (root == end)
					return true;
			}
			else {
				if (populateList(root.left, list, start, end))
					return true;
				if (root == start)
					list = new LinkedList<Node>();
				if (root == end)
					return true;
				return populateList(root.right, list, start, end);
			}
		}

		return false;
	}

O(n^2) solution:

public Line getLine(Point[] points) {
int length = points.length;
int max = 0;
Double maxSlope = 0.0;
Point maxPoint = null;
for (int i = 0; i < length; ++i) {
Point point = points[i];
HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
for (int j = 0; j < length; ++j) {
Point temp = points[j];
double slope = ((temp.y-point.y)*1.0)/(temp.x-point.x);
int count = 1;
if (hm.contains(slope)) {
	count += hm.get(slope);	
}
if (count > max) {
		max = count;
maxSlope = slope;
maxPoint = point;	
}
hm.put(slope, count);
}
 double maxConstant = maxPoint.y-maxSlope*maxPoint.x;
return new Line(maxSlope, maxConstant);
}

An On solution as maximum time any character in the larger string is scanned is 2.

import java.io.*;

public class Qs5389078581215232 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String a = br.readLine();
        String b = br.readLine();

        //Assuming only alphabetic string with lower alphabets
        int[] count = new int[26];
        int lengthA = a.length();
        for (int i = 0; i < lengthA; ++i) {
            char ch = a.charAt(i);
            count[ch-'a']++;
        }

        fill(count, -1);

        int lengthB = b.length();
        int[] temp = copy(count);  
        int start = -1;     
        int matchCount = 0;
        boolean found = false;
        for (int i = 0; i < lengthB; ++i) {
            char ch = b.charAt(i);
            if (temp[ch-'a'] > 0) {
                start = matchCount == 0 ? i : start;
                matchCount++;
                temp[ch-'a']--;
                if (matchCount == lengthA) {
                    found = true;
                    break;
                }
            }    
            else if (temp[ch-'a'] == 0) {
                char tempCh = b.charAt(start);
                while(tempCh != ch) {
                    temp[tempCh-'a']++;
                    matchCount--;
                    start++;
                    tempCh = b.charAt(start);
                }
                start++;    
            }
            else if(temp[ch-'a'] == -1) {
                if (matchCount > 0) {
                    temp = copy(count);
                    matchCount = 0;
                    start = -1;
                }
            }      
        }

        out.println(found);

        out.flush();
        out.close();

        System.exit(0);
    }

    private static int[] copy(int[] A) {
        int lengthA = A.length;
        int[] B = new int[lengthA];

        for (int i = 0; i < lengthA; ++i) {
            B[i] = A[i];
        }
        
        return B;
    }

    private static void fill(int[] A, int num) {
        int lengthA = A.length;
        for (int i = 0; i < lengthA; ++i)
            A[i] = A[i] > 0 ? A[i] : num;
    }
}

I would use the BFS.
a. Color root gray and push it into a queue.
b. Pop from queue one by one. Scan the neighbours of current node based on BFS. If the node to which it is connected is in same level and the node is not black yet add one to count.
c. Color current scnned node to black.

import java.io.*;
import java.util.*;

public class Qs5988741646647296 {
    private final static int WHITE = 0;
    private final static int GRAY = 1;
    private final static int BLACK = 2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int E = Integer.parseInt(br.readLine());
        int V = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < V; ++i) {
            listOfLists.add(new ArrayList<Integer>());
        }        

        for (int i = 0; i < N; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            LinkedList<Integer> list = null;
            if (hm.contains(v1))
                list = hm.get(v1);
            else
                list = new LinkedList<Integer>();
            
            list.add(v2);
            hm.put(v1, list);

            if (hm.contains(v2))
                list = hm.get(v2);
            else
                list = new LinkedList<Integer>();

            list.add(v1);
            hm.put(v2, list);
        }

        boolean[] visitColor = new boolean[V];
        Arrays.fill(visitColor, WHITE);
        
        int[] level = new int[V];

        
        for(int i = 0; i < V; ++i) {
            if (visitcolor[i] == WHITE) {
                Queue<Integer> q = new LinkedList<Integer>();
                q.push(i);
                visitColor[i] = GRAY;
                level[i] = 0;

                int count = 0;

                while(!q.isEmpty()) {
                    Integer num = q.pop();
                    
                    ArrayList<Integer> list = listOfLists.get(num);
                    for (Integer integer:list) {
                        if (visitColor[integer] == WHITE) {
                            q.push(integer);
                            visitColor[integer] = GRAY;
                            level[integer] = level[num]+1;
                        }
                        else if(visitColor[integer] == GRAY)
                            if (level[integer] == level[num])
                              count++;
                    }

                    visitcolor[num] = BLACK;
                }
            }
        }

        out.println(count);
        
        out.flush();
        out.close();

        System.exit(0);
    }
}

import java.io.*;

public class Qs5389078581215232 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String a = br.readLine();
        String b = br.readLine();

        //Assuming only alphabetic string with lower alphabets
        int[] count = new int[26];

        int lengthB = b.length();
        for (int i = 0; i < lengthB; ++i) {
            char ch = b.charAt(i);
            count[ch-'a']++;
        }

        int lengthA = a.length();
        boolean result = true;
        for (int i = 0; i < lengthA; ++i) {
            char ch = a.charAt(i);
            count[ch-'a']--;
            if (count[ch-'a'] < 0) {
                result = false;
                break;
            }
        }

        out.println(result);
        out.flush();
        out.close();

        System.exit(0);
    }
}

Wouldn't using binary search reduce the time complexity further?

Sort the array and then calculate the cost adding element starting from the lowest length.

class Like {
	Post parent = null;
	HashMap<Integer, UserInfo> hm = new HashMap<Integer, UserInfo>();
public Like(Post post) {
	parent = post;
}
public updateLikes(UserInfo info)  {
	if (hm.contains(info.id)) {
		info.likes.remove(this);
hm.remove(info.id);
}
else {
	info.likes.add(this);
	hm.put(info.id, info);
}
}
public int getLikeCount() {
	return hm.size();
}
public ArrayList<UserInfo> getUserList() {
	ArrayList<UserInfo> users = new ArrayList<UserInfo>();
	Set<Map.Entry<Integer, UserInfo>> userSet = hm.entrySet();
	for (Map.Entry<Integer, UserInfo> user : userSet)  {
		users.add(userSet);
	}
	return users;
}
}

O(n) solution:

import java.io.*;
import java.util.*;

public class Question1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; ++i) {
            A[i] = Integer.parseInt(st.nextToken())+1;
        }

        for (int i = 0; i < N; ++i) {
            if (A[i] > 0) {
                int initialVal = A[i];
                int j = i;
                while (A[j]-1 > 0){
                    int temp = A[j]-1;
                    A[j] = -A[temp];
                    j = temp;
                };

                A[j] = -initialVal;
            }
        }
                
        for (int i = 0; i < N; ++i) {
            A[i] = -A[i]-1; 
        }

        out.println(Arrays.toString(A));

        out.flush();
        out.close();

        System.exit(0);
    }
}

import java.io.*;
import java.util.*;

public class PrintDiagonalElements {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int N = Integer.parseInt(br.readLine());

        int[][] mat = new int[N][N];

        StringTokenizer st = null;

        for (int i = 0; i < N; ++i) {
            st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < N; ++j) {
                mat[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int sum = 0; sum < N; ++sum) {
            String prefix = "";
            for (int i = 0; i <= sum; ++i) {
                int j = sum-i;
                out.print(prefix);
                out.print(mat[i][j]);
                prefix = " ";
            }
            out.println();
        }

        for (int sum = N; sum <= 2*N-2; ++sum) {
            String prefix = "";
            for (int i = sum-N+1; i < N; ++i) {
                int j = sum-i;
                out.print(prefix);
                out.print(mat[i][j]);
                prefix = " ";
            }
            out.println();
        }

        out.flush();
        out.close();
              
        System.exit(0);
    }
}

Instead of carrying binary search every time (in a list where we cant jump to a node directly) and reverse traversing the sorted list, you can :
a. Sort list
b. Say first node is min. Find maximum node, max,. s.t. min + max <= K. Push each and every node including it on to a stack.
c. start traversing from first node. Say cur val is cur and it is the ath node (starting from 0th as the first node). Pop stack until cur + popped value <= K. pairCount += no. of stacked element - a (No. of pairs cur makes that are <= K).

public incrementedCount() {
        int carry = 1;
        Node currentNode = head;

        while(true) {
            if (currentNode == null) {
                currentNode = new Node();
                currentNode.data = carry;
                head = currentNode;
            }
            else {
                int num = currentNode.data;
                int sum = num+carry;

                currentNode.data = sum%10;
                carry = sum/10;

                if (currentNode.next == null && carry > 0) {
                    Node next = new Node();
                    next.data = carry;
                    currentNode.next = next;
                    break;
                }
            }
        }
    }

The code assumes the final state required is a <= b >= c <= d ...

Assuming that the avg. word length is S. then sorting the character should be done using count sort instead of quick sort as the range is known and hence a factor of logS can be avoided in sorting.

I see it as a simple BFS traversal problem keeping the predecessor and removing the edges to dangerous island.... Let me know in case I am wrong.

The algorithm is incorrect.. say one of the characters occurs one more time then needle and one character occurs one less time than needle. Instead check the difference of each character. So, complexity is O(26*N)

Why is the answer only one of n or n-1?

The question says at a position k from its actual positions.
So, assuming that we can take an extra array, we start traversing the array.
For element at 0th index we put, kth element.
Similarly for any index i, we find element at (i-k), (i+k) index. We put at that position the leat of the two nos. provided the element is greater or equal to the element at (i-1) index.

Can we assume that the edges of the rectangle are parallel to the X and Y axis?

For 1 1 2 3 4 5
After each element scan :
a. scan 1. count = 2, maximum element = 1
b. scan 1. count = 3 maximum element = 1
c. scan 2. count = 1, maximum element = 1
d. scan 3. count = 0, maximum element = 3
e. scan 5, count = 0, maximum element = 4..

Really nice to use bits to identify common characters.

Try for 1,1,2,3,,4,5

This method is valid only when the max element occurs ore than n/2 times..

int getCount(int[] denom, int value) {
	return getCount(denom, 0, value);
}
int getCount(int[] denom, int index, int reqValue) {
	int value = 0;
	int count = 0;
	if (index == denom.length) {
		return 0;
	}
	while(value < reqValue)
	{
		value += denom[index];
	}
	if (reqValue == value)
		count++;
	value -= denom[index];
	while(value >= 0) {
		count += getCount(denom, index+1, reqValue-value);
		value -= denom[index];
	}
return count;
}

Not able to understand the question.. :(

Well between 901 and 999, there are 33 multiples of 3. All of 3 digits. So total digits = 99. So the 100th digit will be 0.

The solution is HashMap based, O(n)... Say given no is n. At each step, say current no is a, see if :
a. a is present in hashset. If it is present, then print a, n-a.
b. If it is not present save n-a into the hashset.

If you can use O(nlogn) solution sort the array and traverse from left and right. At each step:
a. If the sum is less than n then increment left index.
b. If the sum is greater increment right index.
c. If the sum is equal to n, print the two nos. And decrement left.
f. Repeat the above process. Stop when left > right.

This calls for a recursive solution in which u would at each step check if the left subtree is a BST, right subtree is a BST and the root lies between max of left and min of right subtree.

Found my mistake sorry....

You can use Manacher's algorithm for this :

String getLargestPalString(String S) {
 int T = preProcess(S); // Method arranges '#' in between the char in S, before and after the string
 int C = 0;
 int R = 0;

 int n = T.length();
 int[] P = new int[n];

 for(int i = 1; i < n-1; ++i) {
  int i_mirror = 2*C-i;

  P[i] = (R > i) ? (max(P[i_mirror], R-i)) : 0;
 
  while(T.charAt(i+P[i]+1) == T.charAt(i-P[i]-1))
   P[i]++;

 if(R-i < P[i]) { 
   R = i+P[i];
   C = i;
 }
 }

 //Finding max from P to get largest Pal substring
  int max  = -1;
  int index = -1;

  for(int i = 0; i < n; ++i) {
   if(max < P[i]) {
    max = P[i];
    index = i;
   }
  }

 int C = i/2;
 int start = C-max/2;
 int end = C+max/2-(i&1);
 return S.substring(start, end);
}

The question is not very clear.. By longest sequence what does it mean.. If you are asking Longest Increasing Subsequence... U can use DP and solve in O(n^2) time and O(n) space complexity. :)

Instead of a Hash Map.. we can use int Array. Then memory occupied will b less.... about 32 times less.

Yes probably we can skip calling Arrange 1 time :
a. First scan to get smallest and next to smallest element. Say x, y. Now pass position of second smallest to Arrange to arrange it at last.
b. Scan from 0 to n-2 ignoring smallest x to fet third smallest. Pass position of 3rd smallest to Arrange. keep on doing this till only smallest is left to be arrange. It will by default now b on the first position.

Algo.
Using tabulation :
Keep another matrix Mat[][] with dimension nXm with each element saving both size of max sq matrix till now and its sum.
At any pt. while filling the matrix element (i, j) we have 2 options.. either choose (i-1,j-1) and add to it (i-1, j), (i, j-1) and (i, j) or just choose element (i,j). Out choice will depend on the condition max(sum(i-1,j-1)+A[i-1][j]+A[i][j-1]+A[i][j], A[i][j]) where A is the matrix given.

Code in java:

class Element {
 int size;
 int sum;
}

void printMaxSubmatrix(int[][] A) {
 int n = A.length;
 int m = A[0].length;
 Element[][] Mat = new Element[n][m];
 for(int i = 0; i < n; ++i)
  for(int j = 0; j < m; ++j) 
   Mat[i][j] = new Element();

 int max = -1;
 int row = -1;
 int col = -1;
 for(int i = 0; i < n; ++i) {
  Mat[i][0].size = 1;
  Mat[i][0].sum = A[i][0];
  if(Mat[i][0].sum > max) {
   max = Mat[i][0].sum;
   row = i;
   col = 0;
  }
 }
 for(int i= 0; i <m ; ++i) {
  Mat[0][i].size = 1;
  Mat[0][i] = A[0][i];
  if(Mat[0][i].sum > max) {
   max = Mat[0][i].sum;
   row = 0;
   col = i;
  }
 }

 for(int i = 1; i < n; ++i) {
  for(int j = 1; j < m; ++j) {
   int sum = A[i][j];
   int size = 1;
   if(sum <= Mat[i-1][j-1].sum+A[i-1][j]+A[i][j-1]+A[i][j]) {
    sum = Mat[i-1][j-1].sum+A[i-1][j]+A[i][j-1]+A[i][j];
    size = Mat[i-1][j-1].size+1;
  }
  Mat[i][j].sum = sum;
  Mat[i][j].size = size;
  if(sum > max) {
   max = Mat[i][j];
   row = i;
   col = j;
  }
 }
 
 for(int i = row-Mat[row][col].size+1; i <= row; ++i) {
  for(int j = col-Mat[row][col].size+1; j <= col; ==j) {
   System.out.print(A[i][j]);
 }
System.out.println();
}   
}

Well... I didnt get it.. If say.. we didnt arrange the smallest no. how would we solve?

Qs not clear..

Hi. One possible algo..
Let the array size be n.
start = 0, end = n-1.
The first find smallest no. in [start, end]
give its position to Arrange.
start = 0, end = n-2.
Next find the smallest no. in [start, end] and give its position to Arrange.
Continue till end >= start.
No. of calls to Arrange is n.

Is the string abcdef... handled?

Well.. what you should do is maintain a stack...

For each element say 'X' start popping elements till you find a 'Y' which is smaller that 'X' . Return value of 'Y' and Insert 'X' into the stack.

This ensure a time complexity less than O(n^2). In fact just O(n). Because complexity = No. of pushes = O(n). :)

Using BFS :

private static int BFS(Queue<Node> q) {
		while(!q.isEmpty()) {
			Node node = q.remove();
			int curInd = node.getIndex();
			int curJump = node.getJump();

			if(curInd == N)
				return curJump;
			
			int value = node.getValue();
			
			for(int i = 1; i <= value; ++i) {
				int index = curInd+i;
				int jump = curJump+1;

				if(isSafe(nodes, index)) {
					nodes[index].setColor(COLOR.GREY);
					nodes[index].setJump(jump);
					nodes[index].setParent(curInd);
					
					q.add(nodes[index]);
				}
			}

			node.setColor(COLOR.BLACK);
		}

		return -1;
	}

	private static int getMinJump(Node[] nodes, int start, int end) {
		Queue<Node> q = new LinkedList<Node>();

		nodes[start].setColor(COLOR.GREY);
		nodes[start].setJump(0);
		nodes[start].setParent(-1);

		q.add(nodes[start]);

		return BFS(q);
	}

	private static boolean isSafe(Node[] nodes, int index) {
		return index >= 1 && index <= N && nodes[index].getColor() == COLOR.WHITE;
	}

Also, here in example you are putting an odd element at even index .. as element 1 is put at index 0 and so on.

Cant the original qs be edited instead in mid of discussion ?

#include <stdio.h>
#include <stdlib.h>

//The idea behind the algorithm :
//If even occurs at even OR odd occurs at odd, go to next
//Else stop at wrong index, scan elements after it based on
// a. If elements after that occuring correctly, then just swap with wrong
// b. Else if element not correct and index same type as wrong one, then skip
// c. Else if index of other type, then swap and move to next element
// The method works fine for the cases in the discussion.

main() {
	int *arr;;
	int i, j, k, l, n;

	//Taking input array
	scanf("%d", &n);
	arr = (int *)malloc(sizeof(int)*n);
	for(i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	i = -2;
	j = -1;
	k = 0;
	l = 0;

	//go till end of loop
	while(k < n) {
		//if at even position, an odd element occurs or vice versa
		if((k+arr[k]) & 1L)
		{
			if(l <= k)
				l = k+1;
			else
				l++;
			
			//if right positions, even at even OR odd at odd
			if(!((l+arr[l]) & 1L))
			{	
				int temp = arr[k];
				arr[k] = arr[l];
				arr[l] = temp;
			}
			//if wrong positions
			else
			{
				//if type different from k type
				if((k+l) & 1L)
				{
					int temp = arr[k];
					arr[k] = arr[l];
					arr[l] = temp;
					k++;
				}
			}
		}
		//if the eleeent if right, even at even OR odd at odd
		else
			k++;
	}

	for(i = 0; i < n; i++)
		printf("%3d", arr[i]);
	printf("\n");

	return 0;
}

The answer is still wrong.