LeetCode Q335: Self Crossing (hard)

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return true (self crossing)

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:

There are only three cases where the line will intersect itself.

where red point is the start point.

	class Solution {
	public:
	bool isSelfCrossing(vector<int>& x) {
	if(x.size()<=3)
	return false;
	for(int i = 3; i<x.size(); i++){
	if(x[i-1]<=x[i-3]&&x[i]>=x[i-2])
	return true;
	if(i>=4&&x[i-1]==x[i-3]&&x[i-2]<=x[i]+x[i-4])
	return true;
	if(i>=5&&x[i-2]>=x[i-4] && x[i-4]+x[i]>=x[i-2] && x[i-1]<=x[i-3] && x[i-5] + x[i-1]>=x[i-3])
	return true;
	}
	return false;
	}
	};

view raw Q335.cpp hosted with ❤ by GitHub

LeetCode Q334: Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Solution:

The solution of the question is same to Q300: Longest Increasing Subsequence.

Time complexity O(nlogn)

	class Solution {
	public:
	bool increasingTriplet(vector<int>& nums) {
	if(nums.empty())
	return 0;
	set<int> set;
	for(int i=0; i<nums.size(); i++){
	auto it = set.lower_bound(nums[i]);
	if(it==set.end()){
	set.insert(nums[i]);
	if(set.size()>=3)
	return true;
	}else{
	set.erase(it);
	set.insert(nums[i]);
	}
	}
	return false;
	}
	};

view raw Q334.cpp hosted with ❤ by GitHub

LeetCode Q333: Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one. 
The return value is the subtree's size, which is 3.

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

Solution:

Use solution in Q98. Validate Binary Search Tree to solve this problem.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int helper(TreeNode* root, int& upperBound, int& lowerBound, int& maxNum){
	int res=0;
	if(root==NULL){
	upperBound=INT_MIN;
	lowerBound=INT_MAX;
	return res;
	}
	int lub, llb, rub, rlb;
	int lnum=helper(root->left, lub, llb, maxNum);
	int rnum=helper(root->right, rub, rlb, maxNum);
	lowerBound=root->left==NULL? root->val:llb;
	upperBound=root->right==NULL? root->val:rub;
	if(root->val>=lub&&root->val<=rlb&&lnum!=-1&&rnum!=-1){
	res=lnum+rnum+1;
	maxNum=max(res, maxNum);
	}else
	res=-1;
	return res;
	}
	int largestBSTSubtree(TreeNode* root) {
	int maxNum=0;
	if(root==NULL)
	return maxNum;
	int upperBound, lowerBound;
	helper(root, upperBound, lowerBound, maxNum);
	return maxNum;
	}
	};

view raw Q333.cpp hosted with ❤ by GitHub

LeetCode Q332: Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution:

	class Solution {
	public:
	vector<string> findItinerary(vector<pair<string, string>> tickets) {
	// Each node (airport) contains a set of outgoing edges (destination).
	unordered_map<string, multiset<string>> graph;
	// We are always appending the deepest node to the itinerary,
	// so will need to reverse the itinerary in the end.
	vector<string> itinerary;
	if (tickets.size() == 0){
	return itinerary;
	}
	// Construct the node and assign outgoing edges
	for (pair<string, string> eachTicket : tickets){
	graph[eachTicket.first].insert(eachTicket.second);
	}
	stack<string> dfs;
	dfs.push("JFK");
	while (!dfs.empty()){
	string topAirport = dfs.top();
	if (graph[topAirport].empty()){
	// If there is no more outgoing edges, append to itinerary
	// Two cases:
	// 1. If it searchs the terminal end first, it will simply get
	// added to the itinerary first as it should, and the proper route
	// will still be traversed since its entry is still on the stack.
	// 2. If it search the proper route first, the dead end route will also
	// get added to the itinerary first.
	itinerary.push_back(topAirport);
	dfs.pop();
	}
	else {
	// Otherwise push the outgoing edge to the dfs stack and
	// remove it from the node.
	dfs.push(*(graph[topAirport].begin()));
	graph[topAirport].erase(graph[topAirport].begin());
	}
	}
	// Reverse the itinerary.
	reverse(itinerary.begin(), itinerary.end());
	return itinerary;
	}
	};

view raw Q332.cpp hosted with ❤ by GitHub

LeetCode Q331: Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_

    /   \

   3     2

  / \   / \

 4   1  #  6

/ \ / \   / \

# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:

"9,3,4,#,#,1,#,#,2,#,6,#,#"

Return true

Example 2:

"1,#"

Return false

Example 3:

"9,#,#,1"

Return false

Solution:

Idea is to simulate preorder traversal using a stack. Whenever meet a number, we push it to stack, which is to simulate go along the path down to the bottom left. When it is a #, we pop the stack. There are two situation during this process you should return a false. first, stack becomes empty but there are remaining string. Second, string is empty but stack is not.

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	if(preorder.length()==0)
	return false;
	vector<string> str;
	int i=0;
	string s;
	while(i<=preorder.length()){
	if(preorder[i]==','||i==preorder.length()){
	str.push_back(s);
	s=string("");
	}else{
	s=s+string(1, preorder[i]);
	}
	i++;
	}
	stack<string> myStack;
	i=0;
	while(i<str.size()){
	if(str[i]!="#"){
	myStack.push(str[i]);
	}else{
	if(myStack.empty()&&i!=str.size()-1)
	return false;
	if(!myStack.empty()&&i==str.size()-1)
	return false;
	if(i!=str.size()-1)
	myStack.pop();
	}
	i++;
	}
	return myStack.empty();
	}
	};

view raw Q331.cpp hosted with ❤ by GitHub

Round 2 solution:
When meet a '#', we keep removing '#' and one additional node from the stack. After all available removal, we push back one '#'. So at the end, the valid solution will have only one '#' in the stack.

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	bool res=true;
	stack<string> myStack;
	if(preorder.empty())
	return res;
	int p=0;
	string str;
	while(p<preorder.length()&&preorder[p]!=','){
	str+=string(1, preorder[p]);
	p++;
	}
	p++;
	myStack.push(str);
	str=string("");
	string pre = preorder;
	while(!myStack.empty()&&p<=preorder.length()){
	if(p==preorder.length()||pre[p]==','){
	if(str==string(1, '#')){
	while(!myStack.empty() && myStack.top()==string("#")){
	myStack.pop();
	if(myStack.empty())
	return false;
	myStack.pop();
	}
	myStack.push(string("#"));
	}else{
	myStack.push(str);
	}
	str=string("");
	}else{
	str=str+string(1, pre[p]);
	}
	p++;
	}
	if(myStack.size()==1&&myStack.top()==string("#"))
	return true;
	else
	return false;
	}
	};

view raw Q331Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q329: Longest Increasing Path in a Matrix (hard)

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution 1:

It is not hard to think of DFS. But, its expensive to start a DFS for each entry. When thinking deeper, we notice that, we don't have to do DFS again at some entries if these entries have been accessed before with longest path already computed. To accelerate our computation, we can use memoization to save these information.

	class Solution {
	public:
	int DFS(int row, int col, vector<vector<int> >& matrix, vector<vector<int> >& steps){
	if(steps[row][col]!=0)
	return steps[row][col];
	int maxLen=INT_MIN;
	int dir[8] = {-1, 0, 1, 0, 0, -1, 0, 1};
	for(int i=0; i<4; i++){
	int r = row+dir[i*2];
	int c = col+dir[i*2+1];
	if(r<0||r>=matrix.size()||c<0||c>=matrix[0].size()||matrix[r][c]<=matrix[row][col])
	continue;
	maxLen = max(DFS(r, c, matrix, steps)+1, maxLen);
	}
	steps[row][col]=maxLen==INT_MIN? 1:maxLen;
	return steps[row][col];
	}
	int longestIncreasingPath(vector<vector<int>>& matrix) {
	if(matrix.empty())
	return 0;
	vector<vector<int> > steps(matrix.size(), vector<int>(matrix[0].size(), 0));
	int maxLen=INT_MIN;
	for(int i=0; i<matrix.size(); i++)
	for(int j=0; j<matrix[0].size(); j++)
	maxLen=max(maxLen, DFS(i, j, matrix, steps));
	return maxLen;
	}
	};

view raw Q329.cpp hosted with ❤ by GitHub

LeetCode Q328: Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...

Solution:

Set odd pointer and even pointer, link two pointers to next odd/even nodes alternatively.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* oddEvenList(ListNode* head) {
	if(head==NULL||head->next==NULL)
	return head;
	ListNode* oddHead=head;
	ListNode* evenHead=head->next;
	ListNode* oddp=head;
	ListNode* evenp=head->next;
	while(oddp->next!=NULL&&evenp->next!=NULL){
	oddp->next = evenp!=NULL? evenp->next:NULL;
	oddp=oddp->next;
	evenp->next = oddp!=NULL? oddp->next:NULL;
	evenp=evenp->next;
	}
	oddp->next = evenHead;
	return oddHead;
	}
	};

view raw Q328.cpp hosted with ❤ by GitHub

LeetCode Q327: Count of Range Sum (hard)

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Solution 1:

My solution is to pre-processing the array and compute range sum, than build BST for searching. In C++, to allow duplicated nodes in a BST, you should use multimap.

	class Solution {
	public:
	int countRangeSum(vector<int>& _nums, int lower, int upper) {
	int res=0;
	if(_nums.empty())
	return 0;
	vector<long> nums(_nums.size(), 0);
	nums[0]=_nums[0];
	for(int i=1; i<_nums.size(); i++)
	nums[i]=nums[i-1]+long(_nums[i]);
	multimap<long, long> mySet;
	mySet.insert(pair<long, long>(0, -1));
	for(int i=0; i<nums.size(); i++)
	mySet.insert(pair<long, long>(nums[i], i));
	for(int i=0; i<nums.size(); i++){
	auto hiIt = mySet.upper_bound(nums[i]-lower);
	auto lowIt = mySet.lower_bound(nums[i]-upper);
	for(auto it=lowIt; it!=hiIt; it++)
	if((*it).second<i)
	res++;
	}
	return res;
	}
	};

view raw Q327-1.cpp hosted with ❤ by GitHub

Revised version of solution 1

	class Solution {
	public:
	int countRangeSum(vector<int>& _nums, int lower, int upper) {
	int res=0;
	if(_nums.empty())
	return 0;
	vector<long> nums(_nums.size(), 0);
	nums[0]=_nums[0];
	for(int i=1; i<_nums.size(); i++)
	nums[i]=nums[i-1]+long(_nums[i]);
	multiset<long> sets;
	sets.insert(long(INT_MIN)*5);
	for(int i=0; i<nums.size(); i++){
	auto it = sets.lower_bound(nums[i]-upper);
	if(nums[i]>=lower&&nums[i]<=upper)
	res++;
	if(it!=sets.end())
	for(; it!=sets.end()&&nums[i]-*it>=lower; it++)
	res++;
	sets.insert(nums[i]);
	}
	return res;
	}
	};

view raw Q327sol1-ext.cpp hosted with ❤ by GitHub

Solution 2:
Analysis of the solution is given in this post.

	class Solution {
	public:
	int countRangeSum(vector<int>& nums, int lower, int upper) {
	int size=nums.size();
	if(size==0) return 0;
	vector<long> sums(size+1, 0);
	for(int i=0; i<size; i++) sums[i+1]=sums[i]+nums[i];
	return help(sums, 0, size+1, lower, upper);
	}
	/*** [start, end) ***/
	int help(vector<long>& sums, int start, int end, int lower, int upper){
	/*** only-one-element, so the count-pair=0 ***/
	if(end-start<=1) return 0;
	int mid=(start+end)/2;
	int count=help(sums, start, mid, lower, upper)
	+ help(sums, mid, end, lower, upper);
	int m=mid, n=mid, t=mid, len=0;
	/*** cache stores the sorted-merged-2-list ***/
	/*** so we use the "len" to record the merged length ***/
	vector<long> cache(end-start, 0);
	for(int i=start, s=0; i<mid; i++, s++){
	/*** wrong code: while(m<end && sums[m++]-sums[i]<lower); ***/
	while(m<end && sums[m]-sums[i]<lower) m++;
	while(n<end && sums[n]-sums[i]<=upper) n++;
	count+=n-m;
	/*** cache will merge-in-the-smaller-part-of-list2 ***/
	while(t<end && sums[t]<sums[i]) cache[s++]=sums[t++];
	cache[s]=sums[i];
	len=s;
	}
	for(int i=0; i<=len; i++) sums[start+i]=cache[i];
	return count;
	}
	};

view raw 327-2.cpp hosted with ❤ by GitHub

LeetCode Q325: Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution:

This question remind me of using range sum which require you preprocessing the array and you can get sum of any range in constant time.

Once we preprocess the array, for each location given its range sum starting from 0, to quickly find the part with remaining sum, we should use hash table with range sum as key and array index as content.

	class Solution {
	public:
	int maxSubArrayLen(vector<int>& nums, int k) {
	if(nums.empty())
	return 0;
	unordered_map<int, int> myMap;
	myMap[nums[0]]=0;
	myMap[0]=-1;
	for(int i=1; i<nums.size(); i++){
	nums[i]=nums[i-1]+nums[i];
	auto it = myMap.find(nums[i]);
	if(it==myMap.end())
	myMap[nums[i]]=i;
	}
	int maxv=INT_MIN;
	for(int i=0; i<nums.size(); i++){
	auto it = myMap.find(nums[i]-k);
	if(it==myMap.end())
	continue;
	if(it->second<i)
	maxv=max(maxv, i-myMap[nums[i]-k]);
	}
	return maxv==INT_MIN? 0:maxv;
	}
	};

view raw Q325.cpp hosted with ❤ by GitHub

LeetCode Q324: Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

Solution:

Please refer to this post

	class Solution {
	public:
	void wiggleSort(vector<int>& nums) {
	int n = nums.size();
	int mid = n/2;
	nth_element(nums.begin(), nums.begin() + mid, nums.end());
	threeWayPartition(nums, nums[mid]);
	vector<int> res(n);
	int largeStart = n-1;
	int smallStart = (n%2) ? mid : (mid-1);
	for (int i = 0; i < n; i+=2)
	res[i] = nums[smallStart--];
	for (int i = 1; i < n; i+=2)
	res[i] = nums[largeStart--];
	nums = res;
	}
	// this ensures all values equal to the median is in the middle
	void threeWayPartition(vector<int> &nums, int val) {
	int i = 0, j = 0;
	int n = nums.size()-1;
	while (j <= n){
	if (nums[j] < val)
	swap(nums[i++], nums[j++]);
	else if (nums[j] > val)
	swap(nums[j], nums[n--]);
	else
	j++;
	}
	}
	};

view raw Q324.cpp hosted with ❤ by GitHub

常数空间的解法：

	void wiggleSort(vector<int>& nums) {
	if (nums.empty()) {
	return;
	}
	int n = nums.size();
	// Step 1: Find the median
	vector<int>::iterator nth = next(nums.begin(), n / 2);
	nth_element(nums.begin(), nth, nums.end());
	int median = *nth;
	// Step 2: Tri-partie partition within O(n)-time & O(1)-space.
	auto m = [n](int idx) { return (2 * idx + 1) % (n | 1); };
	int first = 0, mid = 0, last = n - 1;
	while (mid <= last) {
	//可以把Tri-partie好的数组想象成一个隐形的数组，
	//在Tri-partie好数组之后，就可以利用(2 * idx + 1) % (n | 1)来填数字了
	if (nums[m(mid)] > median) {
	swap(nums[m(first)], nums[m(mid)]);
	++first;
	++mid;
	}
	else if (nums[m(mid)] < median) {
	swap(nums[m(mid)], nums[m(last)]);
	--last;
	}
	else {
	++mid;
	}
	}
	}

view raw Q324Rnd3.cpp hosted with ❤ by GitHub

Dutch National Flag Algorithm

Sort an array of 0s, 1s and 2s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

We strongly recommend that you click here and practice it, before moving on to the solution.

The problem is similar to our old post Segregate 0s and 1s in an array, and both of these problems are variation of famous Dutch national flag problem.

The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi–

— Dutch National Flag Algorithm, or 3-way Partitioning —

Part way through the process, some red, white and blue elements are known and are in the “right” place. The section of unknown elements, a[Mid..Hi], is shrunk by examining a[Mid]:

Examine a[Mid]. There are three possibilities: 
a[Mid] is (0) red, (1) white or (2) blue.
Case (0) a[Mid] is red, swap a[Lo] and a[Mid]; Lo++; Mid++




Case (1) a[Mid] is white, Mid++




Case (2) a[Mid] is blue, swap a[Mid] and a[Hi]; Hi--



Continue until Mid>Hi. 

Below is C implementation of above algorithm.

• C
• Java

// C program to sort an array with 0,1 and 2 // in a single pass #include   /* Function to swap *a and *b */ void swap(int *a, int *b);   // Sort the input array, the array is assumed to // have values in {0, 1, 2} void sort012(int a[], int arr_size) {     int lo = 0;     int hi = arr_size - 1;     int mid = 0;       while (mid <= hi)     {         switch (a[mid])         {         case 0:             swap(&a[lo++], &a[mid++]);             break;         case 1:             mid++;             break;         case 2:             swap(&a[mid], &a[hi--]);             break;         }     } }   /* UTILITY FUNCTIONS */ void swap(int *a, int *b) {     int temp = *a;     *a = *b;     *b = temp; }   /* Utility function to print array arr[] */ void printArray(int arr[], int arr_size) {     int i;     for (i = 0; i < arr_size; i++)         printf("%d ", arr[i]);     printf("\n"); }   /* driver program to test */ int main() {     int arr[] = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};     int arr_size = sizeof(arr)/sizeof(arr[0]);     int i;       sort012(arr, arr_size);       printf("array after segregation ");     printArray(arr, arr_size);       getchar();     return 0; }